# Proving existence of a cycle in a directed graph using Lovasz local lemma

Let $$D = (V, A)$$ be a directed graph with minimum outdegree $$\delta$$ and maximum indegree $$\Delta$$. Prove (using Lovasz local lemma) that, if $$k \le 1/(1+\ln(1+\delta\Delta))$$, then $$D$$ contains a directed cycle of length divisible by $$k$$.

This question was asked in one of my class tests. My approach was that I was taking a subset $$V'$$ of vertices of length $$p\times k$$, $$p$$ is some constant greater than $$0$$ and creating a permutation sequence of these vertices. Then I was finding the probability of this sequence being a cycle. I am sure if I'm using the indegree and outdegree correctly also how to use Lovasz local lemma in this?

• I have a question: if $\delta\Delta\geq2$, then $k<1$, so $k=0$ as $k$ should be a non-negative integer. But this seems weird. Perhaps the bound on $k$ is mis-typed here? – awllower Apr 30 at 1:04
• This is Theorem 6.3.1 in cs.cmu.edu/~15850/handouts/matousek-vondrak-prob-ln.pdf – Slugger Aug 1 at 10:39
• @Slugger The referred theorem has condition $k\le\frac\delta{1+\ln(1+\delta\Delta)}$, so the condition here is mis-typed. – awllower Aug 10 at 10:03