5
$\begingroup$

I'm looking for a reference (or proof) for the following claim:

Let $D$ be a directed graph whose outdegrees and indegrees are all equal to $Ck$. Then there are $k$ vertex-disjoint cycles of even length in $D$. Here $C$ is some global constant integer.

There is a similar result using the Lovász Local lemma that shows this for cycles that are not necessarily even, using the weaker assumption that the outdegrees are $=Ck$ and the indegrees are arbitrary. (N. Alon. Disjoint directed cycles. J. Combin. Theory Ser. B, 68(2):167–178, 1996.)

Here we should consider both the indegree and the outdegree: A result due to Thomassen shows that there are digraphs with minimal outdegree arbitrarily large that do not contain any even cycles.

The case $k=1$ is shown in a simple arugment of Alon-Linial to work with $8$-diregular graphs. Their argument is as follows. We randomly 2-color the vertices of $D$. For every vertex $v$, we consider the event that $v$ and its outneighbors are monochromatic. Using the symmetric local lemma we conclude that there is a coloring for which each vertex has an outneighbor of a different color. Then we look at a maximal path for which the colours alternate, and then the endvertex of the path must have an outneighbor in the path of a different color and we found an even cycle. $\square$

If we could partition the vertices so that the induced subgraphs will still have high minimal indegrees and minimal outdegrees then we are done by the case $k=1$, but this cannot be done as-is.

$\endgroup$

1 Answer 1

2
$\begingroup$

To begin with a slight tangent, the paper "Disjoint directed cycles" does not and cannot use the local lemma: a bound on out-degree only isn't good enough if we want to limit the dependencies between bad events in the local lemma. It uses a straightforward probabilistic argument, and relies on a graph-theoretic proof that if the theorem were false, the minimal counterexample could not have too many vertices. I don't think that argument can be replicated here.

However, if you refer to Edge-disjoint cycles in regular directed graphs by Alon, McDiarmid, and Molloy, you get the following result that is proved via the local lemma:

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

In particular, this lemma implies the existence of at least $k/2^{16}$ vertex-disjoint cycles (one in each color).

If you look at the proof of this lemma carefully, a slightly stronger result follows: the $k/2^{16}$ colors come in $k/2^{17}$ pairs such that, for every vertex $v$, it has between $a$ and $4a$ in-neighbors and out-neighbors both in $v$'s color and in the color paired with $v$'s color.

(This is true because Lemma 2 of this paper is used repeatedly to split color classes in two in such a way that each vertex has nearly balanced out-degree and in-degree in the two colors. But Lemma 2 doesn't even check the color of vertex $v$ for its claim about how the neighbors of $v$ are colored, and so the final conclusion follows equally for either of the colors used in the last split relevant to $v$.)

So instead of finding $k/2^{16}$ vertex-disjoint cycles, we can find $k/2^{17}$ vertex-disjoint even cycles: start at a vertex of color $c$ and alternate colors between $c$ and the color $c$ is paired with until you return to a previously seen vertex, and repeat this for all $k/2^{17}$ pairs of colors.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .