%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%      AMSTeX source file for: Partitioning by Monochromatic Trees
% 
%                    P.E. Haxell and Y. Kohayakawa
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%			         Submitted to JCTB
%
%                    Last updated on 26 April 1996
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=\magstephalf
\input amstex
\documentstyle{amsppt}
\refstyle{C}
%
% refdef
%
\newcount\refno\refno=1
\def\referencelabel{\number\refno} 
\def\newrefno{\advance\refno by1}
%
\edef\refnoErGyPy
{\referencelabel}\newrefno
\def\refErGyPy{{\bf[\refnoErGyPy]}}
\edef\refnoFuSurvey
{\referencelabel}\newrefno
\def\refFuSurvey{{\bf[\refnoFuSurvey]}}
\edef\refnoGyHung
{\referencelabel}\newrefno
\def\refGyHung{{\bf[\refnoGyHung]}}
\edef\refnoHaj
{\referencelabel}\newrefno
\def\refHaj{{\bf[\refnoHaj]}}
\edef\refnoRado
{\referencelabel}\newrefno
\def\refRado{{\bf[\refnoRado]}}
\edef\refnoTuzaprep
{\referencelabel}\newrefno
\def\refTuzaprep{{\bf[\refnoTuzaprep]}}
%
% Journals
%
\def\BLMS{Bull. London Math. Soc.}
\def\BAMS{Bull. Amer. Math. Soc.}
\def\JAMS{J. Amer. Math. Soc.}
\def\JLMS{J. London Math. Soc.}
\def\PLMS{Proc. London Math. Soc.}
\def\JCT{J. Combinatorial Theory}
\def\JCTA{J. Combinatorial Theory~(A)}
\def\JCTB{J. Combinatorial Theory~(B)}
\def\JGT{J. Graph Theory}
\def\Comb{Combinatorica}
\def\CPC{Combinatorics, Probability and Computing}
\def\AMASH{Acta Math. Acad. Sci. Hungar.}
\def\SSMH{Studia Sci. Math. Hung.}
\def\EJC{Europ. J. Combinatorics}
\def\GC{Graphs and Combinatorics}
\def\IJM{Israel J. Math.}
\def\DM{Discrete Math.}
\def\ADM{Ann. Discrete Math.}
\def\TAMS{Trans. Amer. Math. Soc.}
\def\PAMS{Proc. Amer. Math. Soc.}
\def\PMH{Periodica Math. Hungar.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\RSA{Random Structures and Algorithms}
% Authors
\def\Aj{Ajtai, M.}
\def\Al{Alon, N.}
\def\Be{Beck, J.}
\def\BB{Bollob\'as, B.}
\def\Chung{Chung, F.R.K.}
\def\Er{Erd\H os, P.}
\def\Fr{Frankl, P.}
\def\Fu{F\"uredi, Z.}
\def\Gra{Graham, R.L.}
\def\Ka{Katona, G.O.H.}
\def\Kl{Kleitman, D.J.}
\def\Ko{Koml\'os, J.}
\def\Lo{Lov\'asz, L.}
\def\Ne{Ne\v set\v ril, J.}
\def\Po{P\'osa, L.}
\def\Ro{R\"odl, V.}
\def\Sey{Seymour, P.}
\def\Sh{Shearer, J.B.}
\def\Si{Simonovits, M.}
\def\So{S\'os, V.T.}
\def\Sp{Spencer, J.H.}
\def\Sz{Szemer\'edi, E.}
\def\Tur{Tur\'an, P.}
\def\Tutte{Tutte, W.T.}
\def\Tu{Tuza, Zs.}
%
% macros
%
\hoffset=1.5truecm
\overfullrule=0pt
\def\({\left(}
\def\){\right)}  
\def\[{\left[}
\def\]{\right]}
\def\e{{\text{\rm e}}}
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\deffont{\it}
%
\newcount\eqnocounter
\eqnocounter=0
\def\slabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  \eqno({\number\eqnocounter})}
\def\alabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  ({\number\eqnocounter})}
%
\def\endclaim{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\claim{\smallbreak\noindent  
  {\it Claim.\enspace}\ignorespaces\bgroup\sl}
  \def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\endassertionsquare{{\unskip\nobreak\hfil\penalty50
  \hskip2em\hbox{}\nobreak\hfil\square
    \parfillskip0pt\finalhyphendemerits=0\par}%
    \egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\assertion(#1){\smallbreak\noindent 
  {\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
\def\endcase{\par\ifdim\lastskip<\smallskipamount
  \removelastskip\penalty3000\smallskip\fi}
\def\case#1.{\smallbreak\noindent 
  {\sl Case\/} #1.\enspace\ignorespaces}
\def\casenodot#1 {\smallbreak\noindent 
  {\sl Case\/} #1\enspace\ignorespaces}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\outer\def\endcasebodysquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
  {\ifdim\lastskip<\smallskipamount\removelastskip\penalty-10\smallskip\fi}}
\def\casebody{\noindent\ignorespaces}
\let\proofofassertion=\casebody
\let\endproofofassertion=\endcasebody
\let\endproofofassertionsquare=\endcasebodysquare
\def\proofoftheclaim{\proofofassertion{\it Proof of the Claim\/}.\enspace}
\let\endproofoftheclaim=\endproofofassertion
%
%
\def\arrow{\to}
%
% new macros
%
%\def\:{{:}\;}
\let\:=\colon
\def\cond{\,\big|\,}
%\def\cond{{\mathrel{\mathop|}}}
\def\G{{\Cal G}}
\def\F{{\Cal F}}
\def\B{{\Cal B}}
\def\cH{{\Cal H}}
\def\E{{\Bbb E}}
\def\P{{\Bbb P}}
\def\Z{{\Bbb Z}}
\def\bd{{\bold d}}
\def\x#1#2{x_{#1}^{(#2)}}
\def\Bi{\mathop{\text{\rm Bi}}\nolimits}
\def\ex{\mathop{\text{\rm ex}}\nolimits}
\def\supp{\mathop{\text{\rm supp}}\nolimits}
%
% statems
%
\newcount\statemno\statemno=1
\def\newstatemno{\advance\statemno by1}
\def\statementlabel{\number\statemno} %new command
%
% intro
%
\edef\MainThm
{\statementlabel}\newstatemno
%
% sec1
%
%\edef\SSz
%{\statementlabel}\newstatemno
%\edef\etaunif
%{\statementlabel}\newstatemno
%\edef\lemmapA
%{\statementlabel}\newstatemno
%\edef\lemmaLocpA
%{\statementlabel}\newstatemno
%
% sec21
%
%\edef\MainOddL
%{\statementlabel}\newstatemno
%\edef\OddCor
%{\statementlabel}\newstatemno
%
% sec22
%
%\edef\WeightL
%{\statementlabel}\newstatemno
%\edef\LocExp
%{\statementlabel}\newstatemno
%
% sec3
%
%\edef\MainDetThm
%{\statementlabel}\newstatemno
%\edef\DetCor
%{\statementlabel}\newstatemno
%
% fstpg
%
\topmatter
\title
Partitioning by Monochromatic Trees
\endtitle
\rightheadtext{PARTITIONING BY MONOCHROMATIC TREES}
\author
P.E.~Haxell and Y.~Kohayakawa 
\endauthor
\address
\noindent
Department of Combinatorics and Optimisation, 
University of Waterloo, Waterloo, Ontario, 
Canada N2L 3G1
\endaddress
\email{\tt<pehaxell\@math.uwaterloo.ca>}
\endemail
\address
\noindent
Instituto de Matem\'atica e Estat\'\i stica, 
Universidade de S\~ao Paulo, Cidade Universit\'aria, 
Rua do Mat\~ao~1010, 05508--900 S\~ao Paulo, SP, 
Brazil
\endaddress
\email{\tt<yoshi\@ime.usp.br>}
\endemail
\keywords Trees, partitioning of graphs, monochromatic subgraphs 
\endkeywords
\subjclass Primary 05C05, 05C35, 05C40; Secondary 05D10
\endsubjclass
\thanks
The first author was partially supported by NSERC.  The second author
was partially supported by FAPESP (Proc.~93/0603--1) and by CNPq 
(Proc.~300334/93--1 and ProTeM-CC-II Project ProComb).   
\endthanks
\abstract Any $r$-edge-coloured $n$-vertex complete graph~$K^n$
contains at most~$r$ monochromatic trees, all of different colours,
whose vertex sets partition the vertex set of~$K^n$,
provided~$n\geq3r^4r!(1-1/r)^{3(1-r)}\log r$.  This comes close to
proving, for large~$n$, a conjecture of Erd\H os, Gy\'arf\'as, and
Pyber, which states that~$r-1$ trees suffice for all~$n$.
\endabstract
\endtopmatter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\document 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% intro
%
\head\S1. Introduction
\endhead
The {\it tree partition number\/} of $r$-edge-coloured complete graphs
is defined to be the minimum $k$ such that whenever the edges of a
complete graph $K^n$ are coloured with $r$ colours, the vertices of
$K^n$ can be covered by at most $k$ vertex-disjoint monochromatic
trees. The {\it cycle partition number\/} is defined similarly. Erd\H
os, Gy\'arf\'as, and Pyber~{\refErGyPy} proved that the cycle
partition number (and hence the tree partition number) is at most
$cr^2\log r$ for some constant $c$. They conjectured in~{\refErGyPy}
that the cycle partition number is $r$, and that the tree partition
number is $r-1$.  Here we prove that the tree partition number is at
most $r$ provided $n$ is sufficiently large with respect to $r$.  Our
main theorem, the proof of which is postponed until the next section,
is as follows.

\proclaim {Theorem {\MainThm}} Let~$r\geq1$
and~$n\geq3r^4r!(1-1/r)^{3(1-r)}\log r$ be integers, and suppose the
edges of~$K^n$ are coloured with~$r$ colours.  Then~$K^n$
contains~$t\leq r$ monochromatic trees~$T_1,\dots,T_t$ of radius at
most~$2$, each of a different colour, such that their vertex
sets~$V(T_i)$ $(1\leq i\leq t)$ partition the vertex set of~$K^n$.
\endproclaim

Note that the lower bound for~$n$ above is, for large~$r$,
about~$3\e^3r^4r!\log r$. As shown in~{\refErGyPy}, the conjecture
for tree partitions is best possible, if true, when $r-1$ is a prime
power. To see this, let $n=(r-1)^2$, and let $K^n$ be a complete graph
whose vertices are labelled with the points of an affine plane of
order $r-1$. Let a colouring of the edges of $K^n$ be given by
assigning colour $i$ to the edge $xy$ if the line through $x$ and $y$
is in the $i$th parallel class. Then each monochromatic component of
this colouring is a complete subgraph of order $r-1$, and so at least
$r-1$ monochromatic trees would be required to partition the set of
vertices. This example can be extended to an example for any $n\geq
(r-1)^2(r-2)$, by replacing each vertex $x$ of $K^{(r-1)^2}$ with a
set of vertices $X$ of size $\lfloor n/(r-1)^2\rfloor$ or $\lceil
n/(r-1)^2\rceil$. Then edge $zw$ for $z\in Z$, $w\in W$ is given
colour $i$ if $Z\not= W$ and the line through $Z$ and $W$ is in the
$i$th parallel class, and colour 1 if $Z=W$. Then the monochromatic
components of this colouring each have at most $(r-1)\lceil
n/(r-1)^2\rceil<n/(r-2)$ vertices, and hence any tree partition would
require at least $r-1$ trees.

The tree partition conjecture for $r=2$ is equivalent to the fact that
either a graph or its complement is connected, an old remark of Erd\H
os and Rado. For $r=3$ the conjecture was proved by Erd\H os,
Gy\'arf\'as, and Pyber~{\refErGyPy}. It was proved by Hajnal
(see~{\refHaj)} that the tree partition number for $r$-edge-coloured
infinite complete graphs is at most $r$.  Rado~{\refRado} proved that
an $r$-edge-coloured countably infinite complete graph may be
partitioned into~$r$ monochromatic, possibly one-way infinite, paths,
generalising a result of Erd\H os, who had proved this statement
for~$r=2$.

A problem that is related to tree partitioning is finding the {\it
  tree cover number\/} for $r$-edge-coloured complete graphs, the
minimum number $k$ such that the vertices of an $r$-edge-coloured
complete graph can be covered by $k$ (not necessarily disjoint)
monochromatic trees. It is clear that this number is at most $r$, as
the set of monochromatic stars centred at any vertex give a cover, and
in the example described previously it is at least $r-1$.  As shown by
Gy\'arf\'as~{\refGyHung}, proving that the tree cover number is $r-1$
is equivalent to proving a conjecture of Lov\'asz and Ryser (see, {\it
  e.g.\/} F\"uredi~{\refFuSurvey}), which states that an $r$-partite
intersecting hypergraph has a transversal of size at most $r-1$. This
was proved by Tuza for $r\leq 5$ in~{\refTuzaprep}.


\head\S2. Proof of Theorem~{\MainThm}
\endhead

Let integers~$r$ and~$n$ as in the statement of the theorem be given.
We may assume that~$r\geq4$.  Suppose the edges of~$K^n$ have been
coloured with colours from~$[r]=\{1,\dots,r\}$.

We start with some definitions.  Let~$s_1=\lceil(n-1)/r\rceil$, and
define the integers~$s_i$ ($2\leq i\leq r$) by letting
$$
s_i=\left\lfloor
      {1\over r-i+1}\(1-{1\over r}\)^2s_{i-1}\right\rfloor.  
\slabel{Rec}
$$
It is clear that the~$s_i$ form a non-increasing sequence. A
straightforward but somewhat tedious calculation shows that~$s_r\geq
r^3\log n$, since~$n$ is assumed to be sufficiently large with respect
to~$r$. (Throughout this note, $\log$ will denote the natural logarithm.)

Let~$B$ be a complete bipartite subgraph of our~$K^n$ with a specified
bipartition~$V(B)=X\cup Y$. Suppose that~$X=\{x_1,\dots,x_t\}$,
where~$1\leq t\leq r$, and~$|Y|\geq s_t$. We say that~$B$ is an {\it
  anchor\/} graph if the colouring of~$K^n$ is such that the colour of
the edge~$x_iy$ ($y\in Y$) depends only on~$x_i$, and this colour is
distinct for each~$x_i$ ($1\leq i\leq t$). We refer to~$t$ as the {\it
  index\/} of~$B$. Thus, an anchor graph of index~$t$ is formed by~$t$
monochromatic stars in~$K^n$, all of distinct colours, and with the
same set of leaves. 

Let~$1\leq t\leq r$ be the largest integer for which~$K^n$ contains an
anchor graph of index~$t$. Fix an anchor graph~$B\subset K^n$ of index~$t$, and
suppose without loss of generality that the edges $x_iy$ ($y\in Y$)
have colour~$i$ for all~$1\leq i\leq t$.

For~$v\in K^n$, $U\subset V(K^n)\setminus\{v\}$, and~$1\leq i\leq r$,
we let~$\Gamma_i(v,U)$ be the set of vertices from~$U$ that are joined
to~$v$ by edges of colour~$i$. Put~$d_i(v,U)=|\Gamma_i(v,U)|$. Observe
that, by the maximality of~$t$, we have~$d_i(z,Y)<s_{t+1}$ for
every~$z\in Z=V(K^n)\setminus V(B)$ and every~$t<i\leq r$.

We now use a simple greedy procedure to find a covering of~$Z$ by
monochromatic stars with centres in~$Y$. To be precise, suppose that,
for some~$q\geq 0$, vertices~$y_1,\dots,y_q\in Y$, colours
$i_1,\dots,i_q\in[t]$, and pairwise disjoint
sets~$Z_1,\dots,Z_q\subset Z$ have been defined such that, for
all~$1\leq k\leq q$, we have
\itemitem{({\it i\/})} $Z_k\subset\Gamma_{i_k}(y_k,Z)$,
\itemitem{({\it ii\/})} putting~$Z_0'=Z$ and~$Z_k'=Z\setminus\bigcup_{j=1}^k
  Z_j$, for $1\leq k\leq q$ we have
$$
|Z_k'|\leq|Z_{k-1}'|\exp\left\{-{1\over tr}\right\}. 
\slabel A
$$

If~$Z=\bigcup_{k=1}^q Z_k$, we have found the desired covering. Thus
suppose that~$Z_q'=Z\setminus\bigcup_{k=1}^q
Z_k\not=\emptyset$. Condition ({\it ii\/}) applied recursively gives
that 
$$
|Z_q'|\leq|Z|\exp\{-q/tr\}<n\e^{-q/tr},
$$
and hence, since~$Z_q'\not=\emptyset$, we deduce that~$q<tr\log n$. As
observed above, $s_r\geq r^3\log n$, whence
$$
s_r>rq. \slabel{KeyIneq}
$$
Therefore~$Y_q'=Y\setminus\{y_1,\dots, y_q\}\not=\emptyset$ since
$|Y|\geq s_t\geq s_r>rq\geq q$. Now to continue the procedure, we let
$y_{q+1}$ and~$i_{q+1}$ be such that~$d_{i_{q+1}}(y_{q+1}, Z'_q)$ is
maximal over all choices of~$y_{q+1}\in Y_q'\not=\emptyset$ and
$i_{q+1}\in[t]$.  Put~$Z_{q+1}=\Gamma_{i_{q+1}}(y_{q+1},Z'_q)$. We now
check that ({\it i\/}) and~({\it ii\/}) hold for~$k=q+1$.  Clearly,
the only work lies in checking~{\eqnoA}. Let us first observe that the
number of edges of colours~$1,\dots,t$ between~$Y_q'$ and~$Z_q'$ is at
least
$$
\sum_{z\in Z_q'}\sum_{1\leq i\leq t} d_i(z,Y_q')\geq
|Z_q'|\big\{|Y|-q-(r-t)s_{t+1}\big\},
$$
where~$s_{r+1}$ is taken to be 0. Thus 
$$
%\eqalign{
%d_{i_{q+1}}(y_{q+1},Z_q')&=\max\{d_i(y,Z_q'):1\leq i\leq t,\;
%  y\in Y_q'\}\cr
%       &\geq{1\over t}\(1-{(r-t)s_{t+1}\over|Y|-q}\)|Z_q'|.\cr
%}
d_{i_{q+1}}(y_{q+1},Z_q')=\max\{d_i(y,Z_q')\:1\leq i\leq t,\;
  y\in Y_q'\}\geq{1\over t}\(1-{(r-t)s_{t+1}\over|Y|-q}\)|Z_q'|.
$$
Hence, putting~$Z_{q+1}'=Z\setminus \bigcup_{k=1}^{q+1}Z_k$, we have
$$
|Z_{q+1}'|\leq\(1-{1\over t}\(1-{(r-t)s_{t+1}\over |Y|-q}\)\)|Z_q'|\leq
|Z_q'|\exp\left\{-{1\over t}\(1-{(r-t)s_{t+1}\over |Y|-q}\)\right\}.
$$
But~$1-(r-t)s_{t+1}/(|Y|-q)\geq1-(r-t)s_{t+1}/(1-1/r)s_t\geq1/r$,
where the first inequality follows from~{\eqnoKeyIneq} and the second
follows from~{\eqnoRec}.
Therefore~$|Z_{q+1}'|\leq|Z_q'|\exp\{-1/tr\}$, as required.

The considerations above show that our procedure terminates with a
covering of~$Z$ by monochromatic stars with centres~$y_1,\dots,
y_{q_0}$, colours~$i_1,\dots,i_{q_0}$, and sets of leaves
$Z_1,\dots,Z_{q_0}$. To complete our tree partition, we define
trees~$T_1,\dots,T_t$ of colours~$1,\dots,t$ as follows. The
tree~$T_i$ ($1\leq i\leq t$) has vertex set
$V(T_i)=\{x_i\}\cup\bigcup(\{y_k\}\cup Z_k)$ and edge set
$E(T_i)=\bigcup (\{x_iy_k\}\cup\{y_kz\:z\in Z_k\})$, where the unions
range over all~$k\in[q]$ with~$i_k=i$. Clearly $\bigcup_{i=1}^t
V(T_i)=X\cup Y_0\cup Z$, where $Y_0=\{y_1,\dots,y_{q_0}\}$. It can be
easily seen that the vertices in~$Y\setminus Y_0$ may be added
to~$T_1$ as leaves to give a tree partition of~$K^n$ as required.
This completes the proof of the theorem. 

\Refs
\ref\key\refnoErGyPy
\by \Er, Gy\'arf\'as, A., Pyber, L.
\paper Vertex coverings by monochromatic cycles and trees
\jour\JCTB
\vol51
\yr1991
\pages 90--95
\endref

\ref\key\refnoFuSurvey
\by F\"uredi, Z.
\paper Matchings and covers in hypergraphs
\jour Graphs and Combinatorics
\vol4
\yr1988
\pages 115--206
\endref

\ref\key\refnoGyHung
\by Gy\'arf\'as, A.
\paper Partition covers and blocking sets in hypergraphs
\inbook MTA SZTAKI Studies,%
        Volume 71 (in Hungarian)
\yr1977
\endref

\ref\key\refnoHaj
\by Hajnal, A., Komj\'ath, P., Soukup, L., Szalkai, I. 
\paper Decompositions of edge coloured infinite complete graphs
\inbook Combinatorics: 7th Hungarian Colloquium, Eger~1987
\bookinfo Colloquia Mathematica Societatis J\'anos Bolyai, Vol~52  
\eds Hajnal, A., Lov\'asz, L., S\'os, V.T.
\publ North-Holland
\publaddr Amsterdam
\yr1988
\pages277--280
\endref

\ref\key\refnoRado
\by Rado, R.
\paper Monochromatic paths in graphs
\inbook Advances in Graph Theory
\bookinfo Annals of Discrete Mathematics~3 
\ed\BB
\publ North-Holland
\publaddr Amsterdam
\yr1978
\pages191--194
\endref

\ref\key\refnoTuzaprep
\by Tuza, Zs.
\paper Some special cases of Ryser's conjecture
\finalinfo preprint
\yr1978
\endref

\endRefs
\enddocument

