Non-periodic paths of length 4 in a graph and the Lovasz Local Lemma

Question

Let $G$ be a graph with maximum degree $\Delta$ and consider colouring its edges, each with one of $k$ colours. A path $v_0v_1v_2v_3v_4$ in a $G$ is $\textit{periodically coloured}$ if $v_0v_1$ and $v_2v_3$ have the same colour and $v_1v_2$ and $v_3v_4$ have the same colour.

a) Prove that $G$ has a colouring with no periodically coloured paths (of length $4$) and at most $\lceil 5\Delta^{3/2} \rceil$ colours.

b) Give a sequence of graphs $G_n$ to show that even if $\Delta$ is fixed and $k > 100\Delta^{3/2}$, the probability that a random $k$-edge-colouring of $G_n$ has no periodically coloured path of length $4$ can be arbitrarily small.

In a) I can give a proof but with $5$ replaced by a larger constant. Consider applying Lovasz Local Lemma (in its symmetric form - see e.g. Theorem 2.3 in https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf) on the events $A_i =$ 'the $i$-th path is periodically coloured'. Clearly $\mathbb{P}(A_i) = \frac{k^2}{k^4} = \frac{1}{k^2}$ and, for any $i$, $d+1 \leq $ 'number of paths of length $4$ which have at least one edge in common with the $i$-th path of length $4$'. (In this number we include the path of $A_i$ itself and that's why we can have $+1$ on the left-hand side.)

Now here's how I estimate the latter number. If the first path is $v_0v_1v_2v_3v_4$, then for the second path there are $4$ choices for which edge of the first path to be common and $4$ choices for what its position in the second path be. After that, there are at most $\Delta^3$ choices for the other three edges from the second path.

So the Local Lemma shall be applicable if $\frac{e}{k^2}16\Delta^3 \leq 1$, but this requires $k\geq \lceil 4e^{1/2}\Delta^{3/2} \rceil$ and unfortunately, $4e^{1/2} \sim 6.59 > 5$. So is there a way to improve the above counting in order to take care of this multiplicative constant issue? Or I somehow need to use the general form of the Local Lemma (but with what real numbers)?

Update: Thanks to Misha Lavrov for the simple example for b).

Any help appreciated!

Answer 1

Actually "4 choices for what its position in the second path be'' could be replaced by 2, since with 4 we count each path twice. For example, if $w$ is the common edge, then in $e_1e_2we_3$ it is in third position, but in $e_3we_2e_1$ it is in second position - however, these two are the same path! With this replacement the required multiplicative constant works out as wanted.

Answer 2

We cannot significantly improve the degree in the dependency graph.

To see this, consider a path $(v_0, v_1, v_2, v_3, v_4)$ in an infinite $\Delta$-regular tree. Starting from each vertex $v_i$, there are at least $\Delta-2$ edges off the path, at least $(\Delta-2)(\Delta-1)$ paths of length $2$, and at least $(\Delta-2)(\Delta-1)^2$ paths of length $3$; if we ignore lower-order terms, these are basically $\Delta, \Delta^2, \Delta^3$ paths that share no edges with this path.

Now, we can get approximately $16 \Delta^3$ distinct paths that overlap with this one as follows:

• Pick $i \in \{0,1,2,3\}$ and $j \in \{0,1,2,3\}$.
• Take the union of a length-$j$ path from $v_i$, the edge $v_i v_{i+1}$, and a length-$(3-j)$ path from $v_{i+1}$; there are roughly $\Delta^j \cdot \Delta^{3-j}=\Delta^3$ choices, and remain so if we make sure not to share any other edges with the path.

Even in a finite graph, we see the same thing if we take a sufficiently large $\Delta$-regular tree, for almost all paths.

---

We should also not expect to benefit from the asymmetric local lemma. That's useful when we have events of legitimately distinct types, but that's not what's happening here.

---

It is possible that we can fix the problem in some other way; maybe we can choose the colors by a different random method. It might help to start with a proper $(\Delta+1)$-edge-coloring, and then randomly determine the color of an edge based on its color in the preliminary coloring somehow.

I think it is more likely that there is a mistake in the constant in the result you are trying to prove.