On Alternating 6-Cycles in Edge-Coloured Graphs
arXiv:2505.09809
summary
The paper shows that, for a large complete graph whose edges are coloured red or blue, the expected number of colour‑alternating 6‑cycles is largest when the colouring is chosen uniformly at random, using the flag algebra method.
Abstract
In this short note, we use flag algebras to prove that the number of colour alternating 6-cycles in a red/blue colouring of a large clique is asymptotically maximized by a uniformly random colouring. This settles the first open case of a problem of Basit, Granet, Horsley, Kündgen and Staden.
19 pages, 2 figures
Topics & keywords
#edge-coloured graphs#alternating cycles#flag algebras#extremal graph theory#random colouringsalternating 6-cyclered/blue colouringcliqueasymptotic maximizationflag algebra method