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$?

  • $\begingroup$ I agree with you that this should've been taken care of in the proof, unless I'm missing something. Here's some thoughts. Denote by $B$ the event that none of the $A_v$ events happen, and by $C$ the event that every color is represented. We'd actually want that $Pr[B \cap C] > 0$, right ? For that, having $P[B | C]$ would be enough. Do you know if the LLL still works fine in this case ? $\endgroup$ – Manuel Lafond Feb 26 '15 at 4:55
  • $\begingroup$ @ManuelLafond I've spoken with the author and he confirmed its a mistake. One would somehow have to include this event C as well. $\endgroup$ – Jernej Feb 26 '15 at 13:08
  • $\begingroup$ Ah, so that's a nice thing you found this out. I've encountered this proof in some textbook, and it had the same mistake. It's sad that errors lurk at every corner in maths and propagate! Anyhow, do you know if only a slight modification of the proof solves it, or if it's major enough to require a whole revision of the proof ? $\endgroup$ – Manuel Lafond Feb 26 '15 at 17:39
  • $\begingroup$ @ManuelLafond Interesting. Where did you find this proof? I think one can fix it by using the asymmetric LLL perhaps at the expense of a worse constant. $\endgroup$ – Jernej Feb 26 '15 at 21:56
  • $\begingroup$ It was right here : books.google.ca/… $\endgroup$ – Manuel Lafond Feb 26 '15 at 22:06

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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.