Rainbow spanning trees in randomly coloured $G_{k-out}$

In our problem, we randomly colour $kn$ edges of $G_{k,q}$ with $q$ colours and we aim to create a rainbow structure. Recall that there are $q_{2}=kn-q\rho$ popular colours that are present $\rho+1$ times and $q_{1}=q-q_{2}$ unpopular colours that are present $\rho$ times.

It is natural to expect that the more colours are available, the easier it is to achieve our goal. We prove this monotonicity property in the following, slightly broader, context. Suppose that we are given a finite set $X$ and a set of colours $C$ where $|C|=|X|$. (In our application, $X$ is the set of $kn$ edges of $G_{k,q}$ and $C$ is the set of $kn$ colours: $q$ colours from set $Q$, including repetitions.) We also have two distinct partitions of $C$: $\mathcal{C}=\{C_{1},\ldots,C_{q}\}$ and $\mathcal{\widehat{C}}=\{\widehat{C}_{1},\ldots,\widehat{C}_{q+1}\}$, for some positive integer $q\leq|X|-1$. (In our application, each part corresponds to a colour from set $Q$. Partitions $\mathcal{C}$ and $\mathcal{\widehat{C}}$ correspond to colourings with $q$ and $q+1$ colours respectively.) Let $\rho={\left\lfloor|X|/q\right\rfloor}$, $\widehat{\rho}={\left\lfloor|X|/(q+1)\right\rfloor}$, $q_{2}=|X|-q\rho$, and $q_{1}=q-q_{2}$. Suppose that $|C_{i}|=\rho$ for $1\leq i\leq q_{1}$ and $|C_{i}|=\rho+1$ for $q_{1}+1\leq i\leq q$, that is, there are $q_{1}$ parts in $\mathcal{C}$ of size $\rho$ and $q_{2}$ parts of size $\rho+1$.

We are given a collection of sets $X_{1},X_{2},\ldots$, each set $X_{i}$ is a subset of $X$. (In our application, the $X_{i}$ are the edges of spanning trees, perfect matchings, Hamilton cycles, etc.) Our goal is to create at least one rainbow set from this collection. Let us consider a random colouring of $X$ via a random bijection from $C$ to $X$. In order to show that the probability that some $X_{i}$ is rainbow in a random colouring with $q+1$ colours is at least the corresponding probability when elements of $X$ are coloured with $q$ colours, we need to couple the two partitions. In order to do that we need to consider two cases.

Case 1: $\widehat{\rho}=\rho$. Partition $\mathcal{\widehat{C}}$ is obtained from $\mathcal{C}$ by choosing $\rho$ parts in $\mathcal{C}$ of size $\rho+1$ and replacing them with $\rho+1$ parts of size $\rho$ (see Figure 1). We couple the two colourings by first randomly mapping the $|C|-\rho(\rho+1)$ colours from the parts that are the same in both partitions, and conditioning on the result. If some rainbow $X_{i}$ is created, then it is clearly present in both colourings. Otherwise, it is easy to see that partition $\mathcal{\widehat{C}}$ is at least as likely to complete a rainbow colouring. Indeed, suppose that some $X_{i}$ has $s$ elements that are not coloured yet; we may assume that $1\leq s\leq\rho$ as, otherwise, such a set cannot be rainbow via the first partition (it could be rainbow via the second partition if $s=\rho+1$). The probability that partition ${\mathcal{C}}$ completes a rainbow colouring is equal to $\prod_{i=1}^{s-1}\frac{\rho(\rho+1)-i(\rho+1)}{\rho(\rho+1)-i}$ that is at most the corresponding probability for partition $\mathcal{\widehat{C}}$, namely, $\prod_{i=1}^{s-1}\frac{\rho(\rho+1)-i\rho}{\rho(\rho+1)-i}$.

Case 2: $\widehat{\rho}=\rho-1$. As before, we start with partition $\mathcal{C}$ but this time we take all $q_{2}$ parts of size $\rho+1$ (possibly $q_{2}=0$ so we might not have any) and we choose $\rho-1-q_{2}$ parts of size $\rho$. To create partition $\widehat{C}$, we replace them with $q_{2}$ parts of size $\rho$ and $\rho-q_{2}$ parts of size $\rho-1$. As in the other case, either we create some rainbow $X_{i}$ or partition $\mathcal{\widehat{C}}$ is at least as likely to complete a rainbow colouring of some set $X_{i}$.

The above coupling allows us to concentrate on the minimum number of colours. In particular, in the proof of Theorem 1, without loss of generality, we may assume that $q=n-1$.

Based on Section 2.1, in order to prove Theorem 1 we may assume that $q=|Q|=n-1$. In this setup, there are $k$ popular colours present $k+1$ times in $G_{k,q}$ and $q-k=n-1-k$ unpopular colours present $k$ times in $G_{k,q}$. Exactly one out of $k+1$ copies of each popular colour is called special. Similarly, there are $k+1$ popular colours present $k+2$ times in $G_{k+1,q}$, $q-(k+1)=n-2-k$ unpopular colours present $k+1$ times, and there are $k+1$ special copies of popular colours (one special copy of each).

It seems reasonable to expect that if $G_{k,q}$ has a particular rainbow structure w.h.p., then so does $G_{k+1,q}$. Let $\Gamma_{k+1}$ be the bipartite graph with vertex sets $[n]$ and $Q^{\prime}=Q\cup\left\{q\right\}$, where $q$ is a “dummy” vertex that will be associated with special copies of popular colours. For each of the $(k+1)$ edges chosen by $v\in[n]$ in $G_{k+1,q}$, we observe a colour $c$ of that edge without exposing its other endpoint. If a copy of colour $c$ is non-special, then we add an edge between $v$ and $c\in Q$ in $\Gamma_{k+1}$; otherwise, we add an edge between $v$ and the “dummy” vertex $q$. Note that we need the extra vertex $q$ to make $\Gamma_{k+1}$ regular.

Recall that $(k+1)n$ colours, including repetitions, are randomly assigned to the $(k+1)n$ edges of $G_{k+1,q}$. Hence, $\Gamma_{k+1}$ is distributed as a random $(k+1)$-regular bipartite (multi)graph (where multiple edges are allowed but not loops). Indeed, it fits the bipartite configuration model of Bollobás [4]. Each vertex could be replaced by a distinct set of $(k+1)$ points, each colour $c\in Q$ naturally corresponds to $(k+1)$ points associated with non-special copies of that colour, and the “dummy” vertex $q$ corresponds to $(k+1)$ points associated with special copies of popular colours. Then, we randomly pair these points to get the colouring of the edges of $G_{k+1,q}$. Note that $\Gamma_{k+1}$ contains no information about the actual vertex choices of edges in $G_{k+1,q}$, only their colour. Informally, we can think of each edge of $\Gamma_{k+1}$ being associated with a box containing a random vertex from $[n]$. We do not need to open these boxes for what is next.

We will use the fact that $\Gamma_{k+1}$ is contiguous to the sum of $(k+1)$ independent random perfect matchings—see the survey on random regular graphs by Wormald [18]. If we delete one of these matchings, then we obtain a random $k$-regular bipartite graph contiguous to $\Gamma_{k}$. Arguing as before, we observe that $\Gamma_{k}$ may be viewed as a random assignment of $kn$ colours, including repetitions, to the $kn$ edges of $G_{k,q}$. “Opening” the boxes on each edge of $\Gamma_{k}$ gives us $G_{k,q}$, which by assumption has a required rainbow structure w.h.p. So, using the above coupling we conclude that $G_{k+1,q}$ also has a rainbow structure w.h.p.

Recall that $k=2$, $q=n-1$, and $\rho={\left\lfloor kn/q\right\rfloor}={\left\lfloor kn/(n-1)\right\rfloor}=2$. There are $q_{1}=q-k=n-1-k=n-3$ unpopular colours that appear $k=2$ times and $q_{2}=k=2$ popular colours that appear $k+1=3$ times.

Note that

	$\displaystyle\mathbb{P}({\cal B}_{\ell})$	$\displaystyle\leq\sum_{t=1}^{3(\ell-1)/2}\binom{n}{t}\sum_{\ell_{1}+\ell_{2}=\ell}\binom{q_{1}}{\ell_{1}}\binom{q_{2}}{\ell_{2}}\binom{tk}{k\ell+\ell_{2}}$
		$\displaystyle\qquad\times\left(\frac{t}{n}\right)^{k\ell+\ell_{2}}\frac{(k\ell+\ell_{2})!}{(kn)(kn-1)\cdots(kn-(k\ell+\ell_{2}-1))},$

where the second sum is taken over all integers $0\leq\ell_{1}\leq q_{1}$, $0\leq\ell_{2}\leq q_{2}$ such that $\ell_{1}+\ell_{2}=\ell$. Indeed, in order to estimate $\mathbb{P}({\cal B}_{\ell})$, we consider all possibilities for $t=|T|\leq 3(\ell-1)/2$ (the first sum) and all sets of size $t$ (the term ${n\choose t}$). We independently consider sets of colours $I\subseteq Q$ with $\ell_{1}$ unpopular colours and $\ell_{2}$ popular ones (the second sum). Then, we need to select specific colours (the term $\binom{q_{1}}{\ell_{1}}\binom{q_{2}}{\ell_{2}}$). Since all edges coloured with $I$ are contained in $T$, we need to select which of the $tk$ edges of $G_{k-out}$ generated by vertices of $T$ are coloured with $I$ (the term $\binom{tk}{k\ell+\ell_{2}}$). The selected edges need to stay within $T$ (the term $\left(\frac{t}{n}\right)^{k\ell+\ell_{2}}$) and be coloured with $I$ (the last term).

Clearly, $\binom{tk}{k\ell+\ell_{2}}\leq(tk)^{k\ell+\ell_{2}}/(k\ell+\ell_{2})!$. Moreover, since $\ell\leq n/20$ and $\ell_{2}\leq q_{2}=k$,

	$\displaystyle(kn)(kn-1)\cdots(kn-(k\ell+\ell_{2}-1))$	$\displaystyle\geq$	$\displaystyle(kn)^{k\ell+\ell_{2}}\left(1-\frac{k\ell+\ell_{2}}{kn}\right)^{k\ell+\ell_{2}}$
		$\displaystyle\geq$	$\displaystyle(kn)^{k\ell+\ell_{2}}\left(\frac{19}{20}+o(1)\right)^{k\ell+\ell_{2}}$
		$\displaystyle=$	$\displaystyle(kn)^{k\ell+\ell_{2}}\left(\sqrt{\frac{20}{19}}+o(1)\right)^{-2(k\ell+\ell_{2})}$
		$\displaystyle\geq$	$\displaystyle(kn)^{k\ell+\ell_{2}}\ 1.03^{-2(k\ell+\ell_{2})}.$

We get that

	$\displaystyle\mathbb{P}({\cal B}_{\ell})$	$\displaystyle\leq$	$\displaystyle\sum_{t=1}^{3(\ell-1)/2}{n\choose t}\sum_{\ell_{1}+\ell_{2}=\ell}\binom{q_{1}}{\ell_{1}}\binom{q_{2}}{\ell_{2}}(tk)^{k\ell+\ell_{2}}\left(\frac{t}{n}\right)^{k\ell+\ell_{2}}\frac{1.03^{\,2(k\ell+\ell_{2})}}{(kn)^{k\ell+\ell_{2}}}$
		$\displaystyle=$	$\displaystyle\sum_{t=1}^{3(\ell-1)/2}{n\choose t}\sum_{\ell_{1}+\ell_{2}=\ell}\binom{q_{1}}{\ell_{1}}\binom{q_{2}}{\ell_{2}}\left(\frac{1.03t}{n}\right)^{2(k\ell+\ell_{2})}.$

Since $\binom{q_{1}}{\ell_{1}}\binom{q_{2}}{\ell_{2}}\leq\binom{q}{\ell}\leq\binom{n}{\ell}\leq(ne/\ell)^{\ell}$, $\binom{n}{t}\leq(ne/t)^{t}$, and $2(k\ell+\ell_{2})\geq 2k\ell=4\ell$, we get

$\displaystyle\mathbb{P}({\cal B}_{\ell})$

$\displaystyle\leq$

$\displaystyle(\ell+1)\sum_{t=1}^{3(\ell-1)/2}\left(\frac{ne}{t}\right)^{t}\left(\frac{ne}{\ell}\right)^{\ell}\left(\frac{1.03t}{n}\right)^{4\ell}.$

Note that since the ratio between the $(t+1)$-st and the $t$-th term is

$$\frac{ne}{t+1}\left(\frac{t+1}{t}\right)^{4\ell-t}\geq\frac{ne}{t+1}\geq 2,$$

the above sum is of the order of its last term. We get that

	$\displaystyle\mathbb{P}({\cal B}_{\ell})$	$\displaystyle=$	$\displaystyle O\left(\ell\left(\frac{ne}{3\ell/2}\right)^{3\ell/2}\left(\frac{ne}{\ell}\right)^{\ell}\left(\frac{1.03\cdot 3\ell/2}{n}\right)^{4\ell}\right)$
		$\displaystyle=$	$\displaystyle O\left(\ell\left(\frac{2}{3}\cdot e^{5/3}\cdot 1.545^{8/3}\ \frac{\ell}{n}\right)^{3\ell/2}\right)$
		$\displaystyle=$	$\displaystyle O\left(\ell\left(\frac{12\,\ell}{n}\right)^{3\ell/2}\right).$

Clearly, $\sum_{\ell=4}^{n/20}\mathbb{P}({\cal B}_{\ell})=O(n^{-6})=o(1)$, since the sum is dominated by its first term.

We first bound the number of pairwise vertex disjoint cycles in $G_{k-out}$, including loops (cycles of length 1) and parallel edges (cycles of length 2). In our application, we concentrate on $k=2$ but the following bound holds in general.

For the next property we need, we assume that $k=2$. As in Section 2.2, let $\Gamma_{2}$ be the bipartite (multi)graph with vertex sets $[n]$ and $Q^{\prime}=Q\cup\{q\}$, where $q$ is a “dummy” vertex associated with special copies of popular colours. There is an edge $vc$ in $\Gamma_{2}$ if one of $v$’s choices has non-special copy of colour $c$; as before, an edge $vq$ occurs in $\Gamma_{2}$ if one of $v$’s choices is one of the two special copies of popular colours. $\Gamma_{2}$ is a random 2-regular bipartite graph. Any 2-regular graph is a collection of cycles. We will use a well-known and easy to prove fact that w.h.p. there are not too many cycles in $\Gamma_{2}$. For completeness, we provide an elementary proof.

We continue concentrating on a minimal $\ell$ (in the range for $\ell$ considered in this section) for which ${\cal A}_{\ell}$ occurs and the corresponding set $I\subseteq Q$. We let $S=C_{I}$ and we expose $G_{S}=([n],S)$, the sub-graph induced by $S$. In particular, $\kappa(S)\geq n-\ell+1$ and we may assume that $G_{S}$ is bridgeless by Claim 1. Let $X_{0}$ denote the number of isolated vertices of $G_{S}$. Since $G_{S}$ is bridgeless, each non-trivial component has a cycle. Hence, the number of non-trivial components, $\eta$, is bounded by the number of pairwise disjoint cycles. By Lemma 3, we may assume that $\eta\leq\frac{3n\log(2k)}{\log n}\leq\frac{5n}{\log n}$. It follows that

$$n-\ell+1\leq\kappa(S)=X_{0}+\eta\text{ where }\eta\leq\frac{5n}{\log n}.$$

(5)

Almost all sets of colours $I$ yield a graph $G_{S}$ with many isolated vertices ensuring that (5) does not hold. Only a small fraction of possible sets of colours need special attention. We will use $\Gamma_{2}$ to estimate how many different configurations we need to take care of.

Let us concentrate on the set of edges incident with colours $I$ in $\Gamma_{2}$, ignoring the two edges incident with a “dummy” vertex $q$. (Note that removing at most two edges from $G_{S}$ may only increase the number of isolated vertices, so $X_{0}\leq X_{0}^{\prime}$, where $X_{0}^{\prime}$ is the number of isolated vertices in $G_{S^{\prime}}$; $S^{\prime}$ is the set obtained from $S$ after removing the edges incident with special copies of popular colours (there are at most two such edges).) By Lemma 4, this set of edges in $\Gamma_{2}$ induces a graph $\Gamma$ consisting of $r\leq(\log n)^{2}$ cycles and $s$ paths. The $2s$ endpoints of paths in $\Gamma$ must be in $[n]$ and so each path corresponds to two distinct non-isolated vertices of $G_{S^{\prime}}$. Let $x$ be the number of vertices in $[n]$ in $\Gamma$ that are of degree 2 (vertices on cycles or internal vertices on paths); they also correspond to non-isolated vertices of $G_{S^{\prime}}$. The remaining vertices in $\Gamma$ are isolated and the corresponding vertices in $G_{S^{\prime}}$ might be isolated. Note that we did not expose edges yet only assigned colours. It is possible that after exposing edges such vertices will be chosen by other ones and become non-isolated. In any case, $X^{\prime}_{0}\leq n-2s-x$. By comparing the number of edges in $\Gamma$ incident to $[n]$ with the number of edges incident to $I\subseteq Q$, we get $2\cdot x+1\cdot(2s)=2\ell$ so $x=\ell-s$. Combining the two observations together, we get $X^{\prime}_{0}\leq n-2s-x=n-\ell-s$.

If $s\geq\frac{5n}{\log n}$, then

$$\kappa(G_{S})=X_{0}+\eta\leq X^{\prime}_{0}+\eta\leq n-\ell-s+\eta\leq n-\ell-\frac{5n}{\log n}+\eta\leq n-\ell,$$

contradicting (5).

Let us assume then that $s<\frac{5n}{\log n}$. Let $V_{0}\subseteq[n]$ denote the set of vertices in $\Gamma$ that are covered by paths and cycles, and let $V_{1}=[n]\setminus V_{0}$. As argued above, $|V_{1}|=n-\ell-s$ and so $|V_{1}|\geq\frac{5000n\log\log n}{\log n}$ since $\ell\leq n-\frac{5001n\log\log n}{\log n}$ and $s<\frac{5n}{\log n}<\frac{n\log\log n}{\log n}$. Vertices in $V_{0}$ correspond to non-isolated vertices in $G_{S^{\prime}}$. Vertices in $G_{S^{\prime}}$ corresponding to vertices in $V_{1}$ that are isolated in $\Gamma$ do not generate any random edges but it does not mean that they are isolated in $G_{S^{\prime}}$. Let $V_{2}\subseteq V_{1}$ denote the set of vertices that are incident with an $I$-coloured edge in $\Gamma$ and are chosen by some vertex in $V_{0}$. It is important to notice that we have not conditioned on the other endpoints of the choices in $\Gamma$ (endpoints of random edges generated by vertices in $G_{S^{\prime}}$ corresponding to vertices in $V_{0}$ in $\Gamma$). We may expose these $2\ell\geq n/10$ edges now, one at a time, each time updating set $V_{2}$. Provided that $|V_{2}|\leq|V_{1}|/50$, we add a new vertex to $V_{2}$ with probability at least $(49|V_{1}|/50)/n\geq|V_{1}|/(2n)$. Let $X\in\text{Bin}\left(n/10,|V_{1}|/(2n)\right)$ with $\mathbb{E}(X)=|V_{1}|/20\geq\frac{250n\log\log n}{\log n}$. The established coupling implies that

$$\mathbb{P}\left(|V_{2}|\leq\frac{|V_{1}|}{50}\right)\leq\mathbb{P}\left(X\leq\frac{|V_{1}|}{50}\right)\leq\mathbb{P}\left(X\leq\frac{\mathbb{E}(X)}{2}\right),$$

and so the Chernoff’s bounds imply that

$$\mathbb{P}\left(|V_{2}|\leq\frac{100n\log\log n}{\log n}\right)\leq\exp\left(-\frac{\mathbb{E}(X)}{12}\right)\leq\exp\left(-\frac{20n\log\log n}{\log n}\right).$$

Now, we need to estimate the number of configurations we need to investigate. After orienting (arbitrarily) cycles in $\Gamma_{2}$, there are at most $\binom{n}{s}$ choices for the beginnings and at most $\binom{n}{s}$ choices for the endings of paths. Such choices yield paths in $\Gamma$. By Lemma 4, there are at most $2^{(\log n)^{2}}$ choices to determine which cycles from $\Gamma_{2}$ should stay in $\Gamma$. Hence, the number of configurations (different bipartite graphs $\Gamma$) we need to deal with is at most

	$\displaystyle\sum_{s<5n/\log n}\binom{n}{s}^{2}2^{(\log n)^{2}}$	$\displaystyle\leq$	$\displaystyle 2\cdot\binom{n}{5n/\log n}^{2}2^{(\log n)^{2}}\leq 2\cdot\left(\frac{en}{5n/\log n}\right)^{10n/\log n}2^{(\log n)^{2}}$
		$\displaystyle\leq$	$\displaystyle\exp\left(\frac{10n\log\log n}{\log n}+O((\log n)^{2})\right)\leq\exp\left(\frac{15n\log\log n}{\log n}\right).$

Comparing it with an upper bound for the failure probability for each configuration, we get that if $s<\frac{5n}{\log n}$ and $|V_{1}|\geq\frac{5000n\log\log n}{\log n}$, then w.h.p. $|V_{2}|>\frac{100n\log\log n}{\log n}$. Since $X^{\prime}_{0}\leq n-\ell-s-|V_{2}|\leq n-\ell-|V_{2}|$, we get that

$$\kappa(G_{S})\leq X^{\prime}_{0}+\eta\leq n-\ell-\frac{100n\log\log n}{\log n}+\eta<n-\ell,$$

contradicting (5).

The two special copies of the two popular colours can give us some unnecessary technical problems in the following calculations. So let us delete the two edges, $e_{1},e_{2}$, associated with special copies so that each colour is used exactly twice. The graph $G^{*}$ obtained this way has $2n-2$ edges. Deleting edges can only increase the number of connected components so it suffices to prove that this quantity is small enough to satisfy (2) after the deletion. It is straightforward to show that $G^{*}$ remains connected w.h.p. but we will not need this fact in our argument.

For the range of $\ell$ considered in this section, it is easier to concentrate on the largest set of colours $I\subseteq Q$ and the associated set of edges $S=C_{I}\cup\{e_{1},e_{2}\}$ for which $G_{S}$ has too many components i.e. $\kappa(G_{S})\geq n-\ell+1$, in violation of (2). Note that for every colour $c$ not in $I$, the two edges of colour $c$ in $G^{*}$ join distinct components of $G_{S}$; otherwise, $I\cup\left\{c\right\}$ also yields a graph with too many components. This means that there are no edges of colour belonging to $Q\setminus I$ in $G^{*}$ joining vertices in the same component of $G_{S}$. Put another way, let ${\mathcal{C}}_{m}$ be the event in $G_{2,q}$ that we can find $m$ colours and the associated $m$ unique pairs of edges $M$ such that

• (i)

  $M\cap\{e_{1},e_{2}\}=\emptyset$,

• (ii)

  each pair in $M$ has the same colour (that is distinct from colours of other pairs in $M$),

• (iii)

  $G_{\bar{M}}=G^{*}-M=G_{2-out}-(M\cup\{e_{1},e_{2}\})$ has at least $m+2$ components, and

• (iv)

  no edge of $M$ joins two vertices of the same component of $G^{*}$.

We have to show that ${\mathcal{C}}_{m}$ is unlikely, for $1\leq m\leq m_{0}:=\frac{5001n\log\log n}{\log n}$.