\documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.49}{24(3)}{2017} \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 Department of Computer Science\\ [-.8ex] \small University of Toronto\\[-0.8ex] \small Toronto, Canada\\ \small\tt molloy@cs.toronto.edu. } \date{\dateline{Feb 1, 2017}{Aug 27, 2017}{Sep 8, 2017}\\ \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,\dots, c_{3\times2^{\ell-1}}$. Because the trees are isomorphic, the sequences $(2^{\la_1(c_1)},2^{\la_1(c_2)},\dots)$ and $(2^{\la_2(c_1)},2^{\la_2(c_2)},\dots)$ 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')$. \medskip\noindent{\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. \subsection*{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\'{a}s 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}