I'm trying to use the Lovász local lemma to prove the following.

Every graph with maximum degree $\Delta$ can be edge-colored (no two adjacent edges have the same color) using $O(\Delta)$ colors so that every cycle contains at least three colors.

The condition that no two adjacent edges have the same color is the same as every vertex having distinct colors. So if $m = O(\Delta)$ is the number of colors, and $A_i$ is the event that at least two edges of $i$ have the same color, then we have that $$ \mathbb{P}(A_i^c) \leq 1\cdot\left(1-\frac{1}{m}\right)\cdots \left(1-\frac{\Delta-1}{m}\right) \sim \prod_{k=0}^{\Delta-1}e^{-k/m} = e^{-\Delta(\Delta-1)/2m}. $$ so that $\mathbb{P}(A_i)$ is about $1-e^{-\Delta(\Delta-1)/2m}$. Since $A_i$ is independent from any $A_j$ such that $j$ and $i$ are not neighbors, we have that $A_i$ depends on $A_j$ for at most $\Delta$ values of $j$. So, for the Lovász local lemma to apply, I would need $$ e(1-e^{-\Delta(\Delta-1)/2m})(\Delta+1) \leq 1 $$ which seems impossible if $m = O(\Delta)$, and we haven't even considered that the cycles must have at least three colors yet!

Any thoughts on how I can continue this problem or other helpful suggestions would be most appreciated.


You'll have an easier time if you don't look at all the edges at a vertex at once. This is generally a good idea with the local lemma: many simple events are better than a few complicated ones. That's because we use the local lemma when the probability of avoiding all events is exponentially small. If you combine several events into one in such a case, you rapidly get into a situation where the conditions of the local lemma can't possibly hold.

If we have an event $A_{uvw}$ (whenever edges $uv,vw$ exist) that $uv,vw$ get the same color, then $\Pr[A_{uvw}] = \frac1m$.

We can combine the edge $uv$ with at most $\Delta-1$ other edges out of $u$ to get another event $A_{xuv}$ entangled with this one, and with at most $\Delta-1$ other edges out of $v$ to get another event $A_{uvx}$ entangled with this one. We can do the same thing with the edge $vw$. This gives us a bound of $4(\Delta-1)$ on the number of other events entangled with $A_{uvw}$. If $e \cdot \frac1m \cdot 4\Delta < 1$, or $m > 4e \Delta$, the local lemma should apply!

Now, for the next part, you'll also have an event $A_C$ for every cycle $C$. You'll have to look at the asymmetric local lemma for this case, giving every event $A_C$ a value $x_C$ satisfying the local lemma condition. $\Pr[A_C]$ is exponentially small in the length of $C$, which is common in this type of problem, so it makes sense to try

  • Assigning each event $A_{uvw}$ the same value $x_2$.
  • Assigning each event $A_C$ where $C$ has length $k$ the same value $x_k = b^k$ for some constant $b \in [0,1]$. (You might as well also assume $x_2 = b^2$.)

Then, play around with the local lemma conditions to figure out the value of $b$ that will make them hold.

  • $\begingroup$ This is wonderful, thank you! I thought I was being clever by finding this equivalence by looking at individual vertices. Your general advice in the first paragraph was very good. I guess part of the power of the LLL is that it does not depend on the number of events you look at, just the number of dependencies of any individual event. $\endgroup$ – MathManiac5772 Apr 11 at 17:57

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.