Unavoidable patterns in locally balanced colourings

Abstract

Which patterns must a two-colouring of $K_n$ contain if each vertex has at least $\epsilon n$ red and $\epsilon n$ blue neighbours? In this paper, we investigate this question and its multicolour variant. For instance, we show that any such graph contains a $t$-blow-up of an \textit{alternating 4-cycle} with $t=\Omega (\log n)$.

Improved exposition