Probabilistic method: vertex disjoint cycles in digraphs

Question

Let us say that a di-graph is $k$-regular if every vertex has precisely $k$ out-edges. The following theorem appears in a book I am currently studying

Theorem. Every $k$-regular graph $D$ has a collection of $r = \lfloor k/(3 \log{k}) \rfloor$ vertex-disjoint cycles.

The proof in the book goes as follows. Color the vertices of $D$ choosing colors from $\{1,\ldots,r\}$ uniformly at random.

For a vertex $v \in V(D)$ define the event $A_v$ that $v$ does not have any out-neighbor of the same color. The author then claims it is enough to show $$Pr[\cap_{v \in V(D)} \overline{A}_v] > 0,$$

and argues how to derive this bound using the Lovasz Local Lemma.

What I am wondering is:

Is there any reason we are disregarding to estimate the probability that each color $r$ is represented in the coloring of $D$?

Answer 1

As already discussed in the comments, the proof is fundamentally flawed. The given probability is positive simply because of the possibility that all vertices could have the same colour; this doesn't require the Lovász local lemma and tells us nothing about the existence of vertex-disjoint cycles.

Answer 2

The book this theorem appears in says that this is a weakening of Lemma 1 from Edge-disjoint cycles in regular directed graphs by Alon, McDiarmid, and Molloy, which says:

If $G$ is a directed graph with no parallel edges, and with minimum degree at least $k\ge 1$ and maximum degree at most $2k$, then the vertices of $G$ may be colored with $k/2^{16}$ colors (each used) in such a way that for each color, the corresponding induced subgraph $H$ has all vertex indegrees and outdegrees in an interval $[a,4a]$ where $a\ge 1$.

The idea of the proof (which we may also use here) is as follows:

1. Use the local lemma to find a $2$-coloring of $V(G)$ which is nearly balanced at each vertex: if a vertex $v$ has in-degree $d$, then its in-degree in each color is in the range $\frac12d \pm d^{2/3}$, and similarly for out-degree.
2. Repeat on each of the two subgraphs we obtain in this way.

In the simpler version stated in the book, however, we can skip step 2 and just do everything in one application of the local lemma. (Assuming, as I think we're intended to, that in a $k$-regular digraph not just the out-degrees but the in-degrees must all be equal to $k$.)

For a vertex $v$, define our bad event $A_v$ to be: not every color is represented at among the out-neighbors of $v$. This differs from the textbook's bad event only in that we don't check $v$'s color; all colors must be represented among the out-neighbors. Now, avoiding every $A_v$ really is enough: each color is represented somewhere, and from each color, we may keep going to an out-neighbor of the same color until we see a vertex twice, creating a cycle in that color.

By the union bound over all $r$ colors, $$\Pr[A_v] \le r \cdot \left(1 - \frac1r\right)^k \le r \cdot e^{-k/r} \le \frac1{3k^2 \log k}$$ while the dependency graph has degree $k^2$ by the same argument as in the textbook: $A_v$ is independent of all $A_w$ for which $N^+(v) \cap N^+(w) = \varnothing$, which leaves $k$ choices of $w \in N^-(x)$ for each of the $k$ vertices $x \in N^+(v)$. The local lemma condition is satisfied when $4 \cdot \frac1{3k^2\log k} \cdot k^2 < 1$ for which we need $k \ge e^{4/3}$. For smaller values of $k$, the statement is trivially true, since $r \le 1$.