🔢 mathematics

On Alternating 6-Cycles in Edge-Coloured Graphs

Using flag algebras, this paper proves that a uniformly random red/blue edge coloring asymptotically maximizes the number of color-alternating 6-cycles in a large clique, thereby resolving the first open case of a problem posed by Basit et al.

Original authors: Hao Chen, Jonathan A. Noel

Published 2026-07-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hao Chen, Jonathan A. Noel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are at a massive party where everyone is wearing either a red shirt or a blue shirt. Now, imagine that every single pair of people at this party has shaken hands, and every handshake is either a "red handshake" or a "blue handshake." This chaotic, colorful web of connections is what mathematicians call an "edge-colored graph." The question that keeps some very curious people up at night is: if you look for a specific pattern in this web—say, a circle of six people where the handshakes alternate colors like Red-Blue-Red-Blue-Red-Blue—how many of these patterns can you possibly find?

This isn't just a party game; it's a branch of mathematics called extremal combinatorics. It's the study of finding the absolute limits of patterns in large systems. Think of it like asking, "What is the most efficient way to arrange bricks to build a wall?" or "What is the maximum number of times you can fold a piece of paper?" In this case, the "bricks" are the handshakes, and the "wall" is the structure of the graph. Mathematicians care about this because understanding these limits helps us understand how order and chaos interact in everything from computer networks to social structures. Sometimes, the most "random" looking arrangement turns out to be the one that creates the most of a specific pattern, and sometimes, a very specific, organized structure is the winner. Figuring out which is which is like solving a cosmic puzzle.

In this short but sharp note, two mathematicians, Hao Chen and Jonathan A. Noel, tackle a specific piece of this puzzle. They wanted to know: in a giant, fully connected party where every handshake is randomly colored red or blue, is that random chaos the best way to maximize the number of those alternating six-person circles (called alternating 6-cycles)?

For a long time, this was an open question. While they knew the answer for some other shapes (like alternating paths or cycles with lengths divisible by four), the case for the 6-cycle was a stubborn mystery. The authors used a powerful mathematical tool called "flag algebras" to crack the code. You can think of flag algebras as a super-charged microscope that allows mathematicians to zoom in on tiny pieces of a graph, count the patterns inside them, and then use those tiny counts to deduce what the whole giant graph must look like. It's a bit like trying to guess the flavor of a giant soup by tasting just a few spoonfuls of ingredients and doing some heavy math on the ratios.

The paper proves a definitive result: The maximum number of these alternating 6-cycles is indeed achieved when the colors are chosen completely at random.

Here is the punchline: If you have a massive clique (a group where everyone is connected to everyone else) and you color the connections randomly—flipping a coin for every handshake to decide if it's red or blue—you will get more alternating 6-cycles than you would with any other clever, pre-planned coloring scheme. The paper shows that the density of these cycles in such a random graph is exactly $(1/2)^6$ , which is $1/64$ .

The authors didn't just guess this; they provided a rigorous proof. They broke the problem down by looking at all the possible ways a small group of six people (specifically, a bipartite graph called $K_{3,3}$ ) could be colored. There are 512 ways to color the edges of this small group with red and blue. By grouping these 512 possibilities into 26 unique "shapes" (ignoring rotations and flips), they were able to set up a massive system of equations.

They introduced a clever trick involving "flags"—small graphs with two special "root" vertices. By analyzing how these flags fit together, they constructed a giant 8-by-8 matrix of numbers. This matrix acts like a mathematical safety net; it is "positive semi-definite," which is a fancy way of saying that no matter how you arrange the colors in your giant graph, the math forces the number of alternating 6-cycles to stay below a certain ceiling. When they crunched the numbers, that ceiling turned out to be exactly $(1/2)^6$ .

So, the paper settles the first open case of a larger problem posed by Basit and colleagues. It confirms that for this specific shape, nature prefers randomness over order. The authors also note that while their method is brilliant for this specific case, it might be too heavy to use for much larger or more complex shapes, as the number of patterns explodes combinatorially. However, their work strongly suggests that for other similar shapes (cycles with lengths like 10, 14, etc.), the random coloring might also be the champion.

Interestingly, the paper mentions that another group of researchers independently reached the same conclusion using similar methods. But for Chen and Noel, the journey was about showing that even in a sea of red and blue chaos, the most "random" arrangement is actually the most productive for creating these specific alternating loops. It's a reminder that sometimes, the best way to build a pattern is to just let the dice roll.

Problem Statement
This paper addresses the "semi-inducibility problem" for edge-coloured graphs, specifically focusing on the maximum density of alternating 6-cycles ( $CA_6$ ) in a large red/blue edge-coloured clique. An alternating cycle $CA_{2k}$ is defined as a cycle where every vertex is incident to exactly one edge of each colour. The central question, posed by Basit et al. [1], is to determine the maximum number of homomorphic copies of such structures in an edge-coloured graph $G$ . While previous work had resolved cases for alternating paths of even and odd lengths, as well as alternating cycles of length divisible by four, the case for alternating cycles of length $2 \pmod 4$ (such as $CA_6$ ) remained open.

Methodology
The authors employ the flag algebra method, a semi-definite programming technique introduced by Razborov [3], to derive an asymptotic upper bound. The proof proceeds through the following technical steps:

Reduction to Injective Homomorphisms: The problem is first reduced from general homomorphisms to injective homomorphisms ( $t_{inj}$ ), showing that proving the bound for injective maps implies the result for general maps via a "blow-up" argument.
Decomposition via $K_{3,3}$ : The authors observe that any injective map from a 6-cycle to a large clique can be analyzed by considering the image of the cycle within a complete bipartite subgraph $K_{3,3}$ . There are $2^9 = 512$ distinct red/blue colourings of $K_{3,3}$ .
Isomorphism Classes and Flags: These 512 colourings are grouped into 26 non-isomorphic classes ( $J_1, \dots, J_{26}$ ). The density of $CA_6$ is expressed as a linear combination of the densities of these 26 classes, weighted by the probability that a random homomorphism from $C_6$ to $K_{3,3}$ maps to a specific class.
Flag Algebra Inequalities: To bound the linear combination, the authors introduce 16 "flags" (graphs with two rooted vertices), denoted $R_1, \dots, R_8$ and $B_1, \dots, B_8$ . They construct an $8 \times 8$ positive semi-definite matrix $A$ . By considering the quadratic forms $\vec{x}_{u,v}^T A \vec{x}_{u,v}$ and $\vec{y}_{u,v}^T A \vec{y}_{u,v}$ (where $\vec{x}$ and $\vec{y}$ represent counts of homomorphisms from the flags to $G$ ), they derive an inequality that relates the density of $CA_6$ to the densities of the 26 isomorphism classes.
Numerical Verification: The proof concludes with a detailed numerical calculation (provided in Appendix A) showing that the coefficients of the densities $d(J_\ell, G)$ in the derived inequality sum exactly to $(1/2)^6$ .

Key Results
The paper establishes the following theorem:
Theorem 1.1: Every edge-coloured graph $G$ satisfies $t(CA_6, G) \le (1/2)^6$ .

The authors demonstrate that this bound is asymptotically tight, as it is achieved by a uniformly random edge-coloured clique. Furthermore, the proof implies that a sequence of edge-coloured cliques achieves this maximum density if and only if the sequence is quasirandom (i.e., the red edges form a quasirandom graph).

Significance and Claims
The paper claims to settle the first open case of the semi-inducibility problem for alternating cycles of length $2 \pmod 4$ (specifically $CA_6$ ), as posed in Problem 9.1 of Basit et al. [1]. The authors note that this result was independently obtained by Balogh, Lidický, Mubayi, and Pfender using similar flag algebra techniques.

Regarding the broader applicability of their method, the authors are modest. They state that the flag algebra method is unlikely to lead to a general proof for all alternating cycles of length $2 \pmod 4$ due to the combinatorial explosion involved in handling graphs with more vertices. However, they suggest that the specific approach used here—relying on the 26 non-isomorphic colourings of $K_{3,3}$ rather than the 156 colourings of $K_6$ , and utilizing flags with missing edges—demonstrates that "simpler" flag algebra proofs might occasionally extend the method's reach or yield human-checkable proofs for theorems that typically require computer verification. The paper does not propose new experimental applications or future research directions beyond these observations.

More like this