Non-periodic paths of length 4 in a graph and the Lovasz Local Lemma 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!
 A: 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.
A: 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.
