
\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amsthm,amsmath,amssymb}


%fullpage specs:
% fullpage.sty use the whole page



\begin{document}


\def\a{\alpha}
\def\b{\beta}
\def\c{\chi}
\def\d{\delta}
\def\D{\Delta}
\def\e{\epsilon}
\def\f{\phi}
\def\F{\Phi}
\def\g{\gamma}
\def\G{\Gamma}
\def\k{\kappa}
\def\K{\Kappa}
\def\z{\zeta}
\def\th{\theta}
\def\Th{\Theta}
\def\l{\lambda}
\def\la{\lambda}
%\def\L{\Lambda}
\def\m{\mu}
\def\n{\nu}
\def\p{\pi}
\def\P{\Pi}
\def\r{\rho}
\def\R{\Rho}
\def\s{\sigma}
\def\S{\Sigma}
\def\t{\tau}
\def\om{\omega}
\def\Om{\Omega}
\def\smallo{{\rm o}}
\def\bigo{{\rm O}}
\def\to{\rightarrow}
\def\E{{\bf E}}
\def\ex{{\bf E}}
\def\cd{{\cal D}}
\def\rme{{\rm e}}
\def\hf{{1\over2}}
\def\R{{\bf  R}}
\def\cala{{\cal A}}
\def\cale{{\cal E}}
\def\Fscr{{\cal F}}
\def\cc{{\cal C}}
\def\calc{{\cal C}}
\def\calh{{\cal H}}
\def\call{{\cal L}}
\def\calr{{\cal R}}
\def\calb{{\cal B}}
\def\calz{{\cal Z}}
\def\bk{\backslash}

\def\out{{\rm Out}}
\def\temp{{\rm Temp}}
\def\overused{{\rm Overused}}
\def\big{{\rm Big}}
\def\notbig{{\rm Notbig}}
\def\moderate{{\rm Moderate}}
\def\swappable{{\rm Swappable}}
\def\candidate{{\rm Candidate}}
\def\bad{{\rm Bad}}
\def\crit{{\rm Crit}}
\def\col{{\rm Col}}
\def\dist{{\rm dist}}

\newcommand\fix{{\rm FIX }}
\newcommand\fixx{{\rm FIX2 }}
\newcommand{\blank}{{\rm Blank }}

\newcommand{\Exp}{\mbox{\bf E}}
\newcommand{\var}{\mbox{\bf Var}}
\newcommand{\pr}{\mbox{\bf Pr}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\newcommand{\limninf}{\lim_{n \rightarrow \infty}}
\newcommand{\proofstart}{{\bf Proof\hspace{2em}}}
\newcommand{\tset}{\mbox{$\cal T$}}
\newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}\vspace{2ex}}
\newcommand{\bfm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\reals}{\mbox{\bfm{R}}}
\newcommand{\expect}{\mbox{\bf Exp}}
\newcommand{\he}{\hat{\e}}
\newcommand{\card}[1]{\mbox{$|#1|$}}
\newcommand{\rup}[1]{\mbox{$\lceil{ #1}\rceil$}}
\newcommand{\rdn}[1]{\mbox{$\lfloor{ #1}\rfloor$}}
\newcommand{\ov}[1]{\mbox{$\overline{ #1}$}}
\newcommand{\inv}[1]{\frac{1}{ #1}}

\def\calc{{\cal C}}
\def\cald{{\cal D}}


\title{A note on the rainbow connection\\ of random regular graphs}
 
\author{Michael Molloy\thanks{Research supported by an NSERC Discovery Grant.}\\
\small Dept of Computer Science\\ [-.08ex]
\small University of Toronto\\[-0.8ex] 
\small Toronto, Canada\\
\small\tt molloy@cs.toronto.edu.  
 }

\date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\
\small Mathematics Subject Classifications: 05C80}

\maketitle

\begin{abstract} We prove that a random 3-regular graph has rainbow connection number $O(\log n)$.  This completes the remaining open case from {\em Rainbow connection of random regular graphs,} by   Dudek, Frieze and  Tsourakakis.
\end{abstract}

\section{Introduction} A {\em rainbow path} in an edge-coloured graph is a path in which every edge has a different colour.
The {\em rainbow connection number} of a graph $G$, denoted $rc(G)$, is the minimum number of colours required to colour the edges of $G$ such that every pair of vertices is connected by a rainbow path.  (The colouring is not required to be proper, although the edge-colourings in this paper will be.) This was introduced by Chartrand et al.\ in~\cite{chart}; see~\cite{li} for a survey and motivations.

$G_{n,r}$ is the random $r$-regular graph on $n$ vertices, where every such graph is selected with equal probability. (We assume that $rn$ is even.)  The diameter of $G_{n,r}$ is approximately $\log_{r-1}n$ with high probability (w.h.p.)\footnote{A property $A$ holds with high probability if $\limninf \Pr(G_{n,r} \mbox{ has } A)=1$.}\cite{bf}; and clearly this is a lower bound on $rc(G_{n,r})$.  Dudek, Frieze and Tsourakakis\cite{dft} proved that $rc(G_{n,r})=O(\log n)$ for $r\geq 4$.  Kamce\u{v}, Krivelevich and Sudakov\cite{kks} provided a short elegant proof for $r\geq 5$ and extended the result to expander graphs and to vertex colourings (for $r\geq 28$).  Here we briefly note that a small modification to the arguments in~\cite{dft} proves their result for $r=3$.

Let $T_1,T_2$ be two copies of a binary tree of height $\ell$, where the roots $x_1,x_2$ have degree three.  We allow an adversary to colour the edges of $T_1,T_2$ so that both colourings are rainbow; i.e. each colour appears at most once in each tree.   $L_i$ is the set of leaves of $T_i$. 
We say a pair of leaves  $u_1 \in L_1,u_2\in L_2$ is {\em compatible} if no colour appears  both in the path from $x_1$ to $u_1$ and in the path from $x_2$ to $u_2$.  We define $M$ to be the number of compatible pairs.

\begin{lemma}\label{l1} For any two rainbow edge colourings of $T_1,T_2$ we have $M\geq 3\times 2^{\ell-1}(2^{\ell-1}+1)$.
\end{lemma}

Since $|L_1|=|L_2|=3\times 2^{\ell-1}$,  more than $\frac{1}{3}$ of the pairs of leaves are compatible.
Lemma 2 of~\cite{dft} proves that the same holds for $d$-ary trees for all $d\geq 3$ (with a root of degree $d$), albeit with a different constant multiple.  

\begin{corollary} W.h.p. $rc(G_{n,3})=O(\log n)$.
\end{corollary}

The proof goes exactly as in~\cite{dft}.  There they first obtain an edge-colouring such that for every vertex $v$, the set of edges within distance $\ell=K\log\log n$ of $v$ is rainbow for a particular constant $K$.  (That set of edges forms a tree for almost every $v$.)  So consider any two vertices $x_1,x_2$, and let $T_1,T_2$  be the trees formed by their distance $\ell$ neighbourhoods.  Applying their Lemma 2 (the analogue of our Lemma~\ref{l1}) they prove that at least one of the  compatible pairs of leaves is joined by a path which contains none of the colours joining either leaf to its root.  For the sake of brevity, we refer the reader to~\cite{dft} for all the details.
\bigskip

\noindent{\bf Proof of Lemma~\ref{l1}}  For each colour $c$ we let $\r(c)$ be the number of pairs $u_1\in L_1,u_2\in L_2$ such that $c$ appears in  both paths from $x_i$ to $u_i$.  Clearly $M\geq |L_1||L_2|-\sum_c\r(c)$ where the sum is taken over all colours $c$ appearing in both trees.  For each such $c$, let $\la_i(c)$ denote the level of the edge in $T_i$ coloured $c$, where the edges adjacent to the leaves are at level $0$ and those adjacent to the root are at level $\ell-1$.  So $\r(c)=2^{\la_1(c)+\la_2(c)}$. 

 Now $\sum_c\r(c)$ is clearly maximized when no colour appears in exactly one tree; so assume that each tree contains the colours $c_1, c_2,..., c_{3\times2^{\ell-1}}$.  Because the trees are isomorphic, the sequences $(2^{\la_1(c_1)},2^{\la_1(c_2)},...)$ and $(2^{\la_2(c_1)},2^{\la_2(c_2)},...)$ are both permutations of the same multiset.  $\sum_c\r(c)$ is the sum of the products of the corresponding elements in those permutations, which is maximized when the permutations are identical. So noting that each tree has $3\times 2^{\ell-\la-1}$ edges at level $\la$, we obtain
\[\sum_c\r(c) \leq \sum_{\la=0}^{\ell-1} 3\times 2^{\ell-\la-1}\times 2^{2\la}
=3\times2^{\ell-1}\times \sum_{\la=0}^{\ell-1}2^{\la} = 3\times2^{\ell-1}\times (2^{\ell}-1).\]
This yields the lemma as $|L_1||L_2|=(3\times2^{\ell-1})^2$.
\proofend


Lemma~\ref{l1} is tight. We will demonstrate this with a recursive edge-colouring of two trees of height $\ell$.
In our construction, $s(u)$ denotes the sibling of $u$, i.e. the other vertex with the same parent as $u$ (which is unique if $u$ is distance at least 2 from the root). For each $u\in T_1$, the corresponding vertex in $T_2$ (i.e. same level and same place in left-to-right order) is  labelled $u'$.

For $\ell=1$, we colour the edges, left-to-right, 1,2,3  for $T_1$ and $3,1,2$ for $T_2$.   To extend from height $\ell$ to $\ell+1$, we use a new set of colours on the new edges of $T_1$, and then use the same colours on $T_2$, this time exchanging the colours of the edges of each pair of siblings; i.e. $u,s(u')$ are joined to their parents by edges of the same colour and so are $s(u),u'$.  

It is not hard to note first that $(u,u')$ is always compatible, and then that each leaf $u\in L_1$ lies in $2^{\ell-1}+1$ non-compatible pairs: $2\times(2^{\ell-2}+1)$ arising from children of nodes who were not compatible with its parent in the previous colouring, plus $s(u')$.

{\bf Remark:} Lemma 2 of~\cite{dft} is stated for  $d$-ary trees, $d\geq 3$, where the root has degree $d$.  Their lemma does not extend to binary trees, as they show with a counterexample (due to Alon) in their section 3.  So the fact that the root has degree 3 in our  Lemma~\ref{l1} is crucial.  Proving Lemma~\ref{l1} when the root has degree 3 is sufficient for the remainder of the argument from~\cite{dft} to apply.  Indeed, \cite{dft} uses their Lemma 2 to derive Corollary 4 which applies to $d$-ary trees with a root of degree $d+1$, and then use Corollary 4 for the remainder of the paper. There is one exception - they use Lemma 3 (which is stated only for trees where the root has degree $d$) in section 2.6.3, but Corollary 4 applies there just as well.

\section*{Acknowledgement}  We thank Alan Frieze for bringing this problem to our attention and for some very helpful discussions.

\begin{thebibliography}{10}
\bibitem{bf} B. Bollob´as and W. Fernandez de la Vega. \newblock The diameter of random regular
graphs. \newblock {\em Combinatorica}, 2:125--134, 1982.

\bibitem{chart} G.Chartrand, G. Johns, K. McKeon and P. Zhang. \newblock Rainbow connection in graphs. \newblock {\em Math. Bohem.},  133:85--98, 2008.
\bibitem{dft} A. Dudek, A. Frieze and C. Tsourakakis. \newblock Rainbow connection of random regular graphs. \newblock
{\em SIAM J. Disc. Math.},  29:2255--2266, 2015.
\bibitem{kks} N. Kamce\u{v}, M. Krivelevich and B. Sudakov. \newblock Some remarks on rainbow connectivity. \newblock {\em J. Graph Theory}, 83:372--383, 2016.
\bibitem{li} X. Li, Y. Shi, and Y. Sun. \newblock Rainbow connections of graphs: a survey. \newblock {\em Graphs
Combin.},  29:1--38, 2013.
\end{thebibliography}

\end{document}
