Maximizing Alternating Paths via Entropy

Abstract

We prove that if $G$ is an $n$-vertex graph whose edges are coloured with red and blue, then the number of colour-alternating walks of length $2k+1$ with $k+1$ red edges and $k$ blue edges is at most $k^k(k+1{)}^{k+1}(2k+1{)}^{-2k-1}{n}^{2k+2}$. This solves a problem that was recently posed by Basit, Granet, Horsley, Kündgen and Staden. Our proof involves an application of the entropy method.