On Alternating 6-Cycles in Edge-Coloured Graphs
Hao Chen, Jonathan A. Noel · 2025
Read On Alternating 6-Cycles in Edge-Coloured Graphs by Hao Chen, Jonathan A. Noel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-09809.txt.
Introduction
Hao Chen and Jonathan Noel settle a question about alternating color patterns in fully connected networks, in a 2025 note. Color every link red or blue, and count the six-node cycles whose colors alternate around the loop.
A problem posed by five researchers asked which coloring produces the most such cycles in a large network. Using flag algebras, a method that reasons about small patterns at scale, the authors prove that random coloring wins, at least asymptotically. The result closes the first open case of the problem. It also shows the power of flag methods on concrete counting questions in extremal combinatorics.
Catalog record
| CREATOR | Hao Chen, Jonathan A. Noel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-09809
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Alternating 6-Cycles in Edge-Coloured Graphs Hao Chen, Jonathan A. Noel Abstract In this short note, we use flag algebras to prove that the number of colour alternating 6 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. 1 Introduction An edge-coloured graph is a graph whose edges are coloured red or blue. For k\geq 2 , the alternating cycle C_{2k}^{A} is the edge-coloured graph consisting of the cycle graph C_{2k} where every vertex is incident to exactly one edge of each colour. Our goal is to determine the maximum number of “copies” of the alternating 6 -cycle in a large edge-coloured graph G . Here, when speaking of “copies,” we mean “homomorphic copies.” More precisely, a homomorphism from an edge-coloured graph H to an edge-coloured graph G is a map f:V(H)\to V(G) with the property that if uv is a edge of H , then f(u)f(v) is an edge of G with the same colour as uv . Let \hom(H,G) be the number of homomorphisms from H to G . The homomorphism density of H in G is t(H,G)=\hom(H,G)/v(G)^{v(H)} . The following theorem solves the first case of a problem posed recently by Basit et al. [ 1 , Problem 9.1] . Theorem 1.1 . Every edge-coloured graph G satisfies t(C_{6}^{A},G)\leq(1/2)^{6} . It is not hard to see that this is asymptotically tight by taking G to be a uniformly random edge-coloured clique on a large number of vertices. Our proof of Theorem 1.1 , provided in the next section, is a relatively simple application of the flag algebra method of Razborov [ 3 ] . The problem of determining the maximum density of copies of an edge-coloured graph H in an edge-coloured graph G , called the semi-inducibility problem , was introduced recently by Basit et al. [ 1 ] , who solved it for several classes of graphs including alternating paths of even length and alternating cycles of length divisible by four. In a recent paper together with Clemen, we used entropy to settle the case of alternating paths of odd length [ 2 ] . It would be interesting to solve the semi-inducibility problem for alternating cycles of length 2\bmod 4 in full generality [ 1 , Problem 9.1] . The method in the present paper is, unfortunately, unlikely to lead to a general proof, but it does suggest that the correct bound may be of the form t(C_{4k+2}^{A},G)\leq(1/2)^{4k+2} . Remark 1.2 . We are aware that another group of researchers, Balogh, Lidický, Mubayi and Pfender (personal communication), independently proved Theorem 1.1 using flag algebras and have obtained other related results. 2 The Proof Our first step in the proof of Theorem 1.1 is to reduce it to a statement about injective homomorphisms. For edge-coloured graphs H and G with v(G)\geq v(H) , let \hom_{\inj}(H,G) be the number of injective homomorphisms from H to G ; when v(G)<v(H) , then we let \hom_{\inj}(H,G):=0 . Also, define t_{\inj}(H,G):=\frac{(v(G)-v(H))!}{v(G)!}\hom_{\inj}(H,G) . That is, t_{\inj}(H,G) is the probability that a uniformly random injective function from V(H) to V(G) is a homomorphism. We show that Theorem 1.1 can be deduced from the following theorem; after this, we focus the rest of the paper on proving Theorem 2.1 . Theorem 2.1 . Every edge-coloured graph G satisfies t_{\inj}(C_{6}^{A},G)\leq(1/2)^{6}+o(1) . Proof of Theorem 1.1 , assuming Theorem 2.1 . Suppose that there exists an edge-coloured graph G such that t(C_{6}^{A},G)>(1/2)^{6} . For each N\geq 1 , let G_{N} be the edge-coloured graph obtained by “blowing up” each vertex of G into a set of size N . That is, G_{N} is the edge-coloured graph consisting of N\cdot v(G) vertices divided into v(G) classes of size N , one for each vertex of G , where the edges between two classes are the same colour as the edge between the corresponding vertices of G . It is easily observed that \lim_{N\to\infty}t_{\inj}(C_{6}^{A},G_{N})=t(C_{6}^{A},G) and so, for large enough N , the graph G_{N} contradicts Theorem 2.1 . ∎ We prove Theorem 2.1 . Let G be an edge-coloured graph on n vertices. Our aim is to prove that t_{\inj}(C_{6}^{A},G)\leq(1/2)^{6}+o(1) . We may assume that G is an edge-coloured clique; this is because adding any missing edge with an arbitrary colour cannot decrease t_{\inj}(C_{6}^{A},G) . There are 2^{9}=512 distinct red/blue edge colourings of the complete bipartite graph K_{3,3} . Let H_{1},\dots,H_{512} be the corresponding edge-coloured graphs where, for convenience, we assume V(K_{3,3})=V(H_{1})=\cdots=V(H_{512}) . Since G is a clique, for any injective function f:V(K_{3,3})\to V(G) , there is a unique index i\in\{1,\dots,512\} such that f is a homomorphism of H_{i} to G . Thus, \sum_{i=1}^{512}t_{\inj}(H_{i},G)=1. (2.2) Of course, among the 512 distinct edge-colourings of K_{3,3} , many of them are isomorphic to one another. Up to isomorphism, there are 26 different red/blue edge colourings of the complete bipartite graph K_{3,3} . Let J_{1},\dots,J_{26} be the corresponding 26 edge-coloured graphs, as depicted in Figure 1 , where V(J_{\ell})=V(K_{3,3}) for all 1\leq\ell\leq 26 . J_{1} J_{2} J_{3} J_{4} J_{5} J_{6} J_{7} J_{8} J_{9} J_{10} J_{11} J_{12} J_{13} J_{14} J_{15} J_{16} J_{17} J_{18} J_{19} J_{20} J_{21} J_{22} J_{23} J_{24} J_{25} J_{26} Figure 1: The 26 edge colourings of K_{3,3} up to isomorphism. Red edges are drawn as solid lines and blue edges are drawn as dashed lines. For an edge-coloured graph H , an automorphism of H is a bijective homomorphism from H to itself. Let \aut(H) be the number of automorphisms of H . For each J_{\ell} , the number of indices j\in\{1,\dots,512\} such that J_{\ell} is isomorphic to H_{j} is precisely \frac{2\cdot 3!\cdot 3!}{\aut(J_{\ell})}=\frac{72}{\aut(J_{\ell})} . Therefore, if we let d(J_{\ell},G):=\frac{72}{\aut(J_{\ell})}t_{\inj}(J_{\ell},G) for each 1\leq\ell\leq 26 , then ( 2.2 ) can be rewritten as \sum_{\ell=1}^{26}d(J_{\ell},G)=1. (2.3) A homomorphism between two graphs without edge colours is simply a map from the vertex set of the first graph to the vertex set of the second with the property that adjacent pairs of vertices are mapped to adjacent pairs of vertices. We view the graph C_{6} and the edge-coloured graph C_{6}^{A} as having the same vertex set. For each 1\leq i\leq 26 , let t_{\bip}(C_{6}^{A},J_{\ell}) be the probability that a uniformly random injective homomorphism f from C_{6} to K_{3,3} is a homomorphism from C_{6}^{A} to J_{\ell} ; we define t_{\bip}(C_{6}^{A},H_{i}) analogously for 0\leq i\leq 512 . The next proposition relates t_{\inj}(C_{6}^{A},G) to the quantities t_{\bip}(C_{6}^{A},J_{\ell}) and d(J_{\ell},G) for 1\leq\ell\leq 26 . Proposition 2.4 . For any edge-coloured clique G , t_{\inj}(C_{6}^{A},G)=\sum_{\ell=1}^{26}t_{\bip}(C_{6}^{A},J_{\ell})\cdot d(J_{\ell},G). Proof. If v(G)<6 , then both sides of the equation in the proposition are zero and so we may assume that v(G)\geq 6 . Let f:V(K_{3,3})\to V(G) be a uniformly random injective function and let g:V(C_{6})\to V(K_{3,3}) be a uniformly random injective homomorphism from C_{6} to K_{3,3} . Then f\circ g is nothing more than a uniformly random injective function from V(C_{6}^{A}) to V(G) . Let E be the event that f\circ g is a homomorphism from C_{6}^{A} to G and, for each 1\leq i\leq 512 , let F_{i} be the event that f is a homomorphism from H_{i} to G . By definition, we have