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?

  • 1
    $\begingroup$ 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? $\endgroup$ – awllower Apr 30 at 1:04
  • 1
    $\begingroup$ This is Theorem 6.3.1 in cs.cmu.edu/~15850/handouts/matousek-vondrak-prob-ln.pdf $\endgroup$ – Slugger Aug 1 at 10:39
  • $\begingroup$ @Slugger The referred theorem has condition $k\le\frac\delta{1+\ln(1+\delta\Delta)}$, so the condition here is mis-typed. $\endgroup$ – awllower Aug 10 at 10:03

Your Answer

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

Browse other questions tagged or ask your own question.