REVIEW 3 major objections 3 minor 2 cited by
On Alternating 6-Cycles in Edge-Coloured Graphs
T0 review · 3 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Every edge-coloured graph has at most $(1/2)^6$ alternating 6-cycles per 6-vertex set, with equality approached only by random colourings.
desk verdict Proves the first open case of the semi-inducibility problem for alternating 6-cycles with a clean flag algebra argument, but the key inequality depends on an uncertified positive semidefiniteness claim. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof reduces the problem to injective homomorphisms, partitions the $512$ red/blue colourings of $K_{3,3}$ into the $26$ isomorphism classes $J_1,\ldots,J_{26}$, and expresses the alternating-6-cycle density as a linear combination of the class densities $d(J_\ell,G)$. The core object is an $8\times 8$ matrix $A$ together with sixteen rooted flags $R_1,\ldots,R_8$ and $B_1,\ldots,B_8$; because $A$ is asserted positive semidefinite, the quadratic forms $\vec{x}_{u,v}^T A \vec{x}_{u,v}$ and $\vec{y}_{u,v}^T A \vec{y}_{u,v}$ are nonnegative. Adding these nonnegative terms to the expression for $t_{\mathrm{inj}}(C_6^A,G)$ and double-counting the resulting products of flag densities yields exactly $(1/2)^6\sum_{\ell=1}^{26} d(J_\ell,G) + o(1)$.
What would settle it
Compute the eigenvalues of the $8\times 8$ matrix $A$ printed in Section 2; if any eigenvalue is negative, the inequality (2.6) is not justified and the proof collapses. Alternatively, run a computer search over edge-coloured cliques on 8–10 vertices for one whose alternating-6-cycle homomorphism density exceeds $1/64$.
Extended reading notes
Core claim
The central claim is Theorem 1.1: every edge-coloured graph $G$ satisfies $t(C_6^A, G) \leq (1/2)^6$. Since the uniformly random colouring of a large clique has alternating-6-cycle density $(1/2)^6 + o(1)$, this identifies random colouring as the asymptotic extremal configuration. The proof further shows that a sequence of edge-coloured cliques approaches density $(1/2)^6$ if and only if the sequence is quasirandom, meaning every edge-coloured pattern appears with the frequency expected from a random colouring.
Load-bearing premise
The 8-by-8 matrix $A$ is asserted, without proof or certificate, to be positive semidefinite, and the entire upper-bound inequality (2.6) depends on that assertion.
Editorial extensions
If this is right
- Every edge-coloured graph has alternating-6-cycle homomorphism density at most $(1/2)^6$, so no red/blue pattern can beat a random colouring.
- The extremal sequences are exactly the quasirandom ones: approaching the maximum forces the red graph to be quasirandom.
- This solves the first open case of the semi-inducibility problem for alternating cycles.
- The paper suggests, but does not prove, the general bound $t(C_{4k+2}^A, G) \leq (1/2)^{4k+2}$ for all $k \geq 1$.
- The unusually small flag set (16 flags rather than 40) hints that flag-algebra proofs with missing edges and bipartite ambient graphs may apply to larger alternating cycles.
Reading between the lines
- Because extremality implies quasirandomness, the alternating 6-cycle is a forcing object: a single subgraph density constraint forces the entire colouring to be random, a phenomenon that may hold for every alternating cycle of length $2 \bmod 4$.
- A short rational Cholesky decomposition of the $8\times 8$ matrix $A$ would turn the asserted positive semidefiniteness into a human-checkable certificate, making the proof fully verifiable without computer algebra.
- The use of $K_{3,3}$ rather than $K_6$ suggests a general template: for alternating $2k$-cycles, one might work with $K_{k,k}$ colourings and rooted flags with missing edges, which could keep the flag count manageable for $k=5$ or $6$.
- If the suggested bound $t(C_{4k+2}^A, G) \leq (1/2)^{4k+2}$ holds, then random colourings simultaneously extremize all alternating cycles of length $2 \bmod 4$, strengthening the case for a general semi-inducibility theorem.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that in every red/blue edge-coloured graph G, the homomorphism density t(C^A_6, G) of the colour-alternating 6-cycle is at most (1/2)^6, with equality asymptotically for uniformly random colourings. The proof follows the flag algebra method: it reduces to injective homomorphism densities, partitions the copies of K_{3,3} into 26 isomorphism types, derives an expression for tinj(C^A_6, G) as a weighted combination of the densities d(J_ℓ, G), introduces 16 rooted flags, and proves the desired upper bound by adding two positive semidefinite quadratic forms based on an 8×8 matrix A. The proof concludes by computing, for each of the 26 types J_ℓ, that the coefficient of d(J_ℓ, G) is (1/2)^6. The final paragraph outlines an argument that extremality forces quasirandomness.
Significance. If the proof is correct, this solves the first open case of a problem of Basit, Granet, Horsley, Kündgen and Staden on semi-inducibility of alternating cycles, showing that random colourings are asymptotically extremal for C^A_6. The paper has two notable strengths: the reduction from homomorphism densities to injective densities via the blow-up argument is clean, and the flag algebra certificate is unusually small and presented in human-readable form, sparing the reader the large semidefinite programs typical of such proofs. The paper also correctly credits independent work of Balogh, Lidický, Mubayi and Pfender. However, the main result rests on two computational assertions that are not actually proved: the positive semidefiniteness of the matrix A and the correctness of the long tables of tbip values. Both are load-bearing, so the current manuscript is not yet a complete proof.
major comments (3)
- [Section 2, definition of A] The claim 'The matrix A is positive semi-definite (i.e. all of its eigenvalues are non-negative)' is the only justification for the inequalities x^T A x ≥ 0 and y^T A y ≥ 0 that are used in (2.6). This is a load-bearing step: if A had any negative eigenvalue, the expression in (2.6) would not be an upper bound for tinj(C^A_6, G). The paper does not provide a proof or certificate for this assertion. I verified that all row sums are zero, so the all-ones vector is in the kernel, but the remaining eigenvalues are not shown. Please provide a verifiable certificate, such as an exact Cholesky factorization A = LL^T with rational entries, a list of all eigenvalues with algebraic or numerical verification, or a sum-of-squares decomposition of the quadratic form. Without this, the central inequality (2.6) is unsupported.
- [Section 2, tbip tables] The displayed formulas for tinj(R_i · R_j, G) and tinj(B_i · B_j, G) (36 + 36 identities) are introduced with 'By computing the quantities tbip(...) explicitly ... we obtain the following:' and no further derivation. These formulas are used as input to the coefficient calculations that prove every coefficient of d(J_ℓ, G) equals (1/2)^6, so if any one of them is wrong the proof fails. The computation is in principle checkable by direct enumeration, but as written it is a bare assertion. Please provide either a human-readable derivation (e.g., the generating table of tbip values for each pair (i,j) and each J_ℓ) or a short computer script that verifies all of them, to make the proof independently checkable.
- [Section 2, coefficient calculations] The arithmetic showing that each coefficient of d(J_ℓ, G) in (2.6) equals (1/2)^6 is long and not machine-verified in the manuscript. While the displayed sums are explicit, the sheer number of terms makes this a possible source of transcription errors. In particular, the line for J11 contains the garbled fragment 'J11: 1/12 1/6+ +' which appears to be a typesetting mistake; the actual computation is interleaved with the J9 and J12 computations. Please audit the coefficient listings and include the global calculation in a more transparent form (e.g., a table of the final coefficient for each J_ℓ, or an appendix with the complete arithmetic) so that the conclusion that (2.6) evaluates to (1/2)^6 + o(1) can be checked without manual re-entry of every term.
minor comments (3)
- [Abstract] The abstract says 'the number of colour alternating 6-cycles', but the paper actually studies homomorphism densities (and, via Theorem 2.1, injective homomorphism densities). Please clarify the phrasing to reflect the formal definition used in the paper.
- [Final paragraph] The quasirandomness characterization is stated only as a brief summary. Since it also relies on the unproved assertion that the kernel of A is spanned by the all-ones vector, please either prove it in full or clearly label it as a conjecture/remark. As written, it is a stronger claim than Theorem 1.1 and would require the same computational certificate.
- [References] Reference [1] is to a preprint arXiv:2501.09842v1; reference [2] is to another preprint. Please add any published or more stable versions if they have appeared, and in Remark 1.2 the independent work of Balogh, Lidický, Mubayi and Pfender is mentioned without a bibliographic entry; a citation after their work becomes public would be appropriate.
Circularity Check
No circularity found: the flag-algebra proof is a direct, self-contained sum-of-squares argument whose only unverified step is a PSD assertion, which is a verification gap rather than an input-output equivalence.
full rationale
The paper's derivation is a standard flag-algebra proof: it reduces the homomorphism density of the alternating 6-cycle to injective densities, decomposes K_{3,3} colourings into 26 isomorphism classes, computes the relevant conditional probabilities, and then adds explicit quadratic forms x^T A x and y^T A y to obtain the upper bound in (2.6). The matrix A is a fixed 8x8 matrix of rational numbers; it is not fitted to data, not defined in terms of the target density, and not imported from any prior work of the authors. The subsequent coefficient-by-coefficient calculations are explicit and independently checkable, and every coefficient of d(J_l,G) in (2.6) is shown to equal (1/2)^6. The only load-bearing assertion without proof is 'The matrix A is positive semi-definite'; if false, the inequality in (2.6) would not follow. However, this is a missing certificate or verification gap, not a circular step: the proof does not assume the upper bound it is trying to prove, and the PSD property is not equivalent to the target result by construction. The quasirandomness characterization at the end is likewise derived from the kernel of A and standard quasirandomness results, not from assuming the extremal configuration. Self-citations to the authors' entropy paper are background only and do not carry the argument. No fitted input is renamed as a prediction, no uniqueness theorem is imported from the same authors, and no known result is merely relabelled. Therefore the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (2)
- ad hoc to paper The 8x8 matrix A in Section 2 is positive semidefinite.
- ad hoc to paper The listed explicit formulas for tinj(Ri·Rj,G) and tinj(Bi·Bj,G) are correct.
Cite this review
Pith. "Pith review of On Alternating 6-Cycles in Edge-Coloured Graphs." pith.science (2026). https://pith.science/paper/UBDADCCI
@misc{pith2026250509809,
author = {Pith},
title = {Pith review of: On Alternating 6-Cycles in Edge-Coloured Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/UBDADCCI}},
note = {Machine review of arXiv:2505.09809}
}
read the original 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\"undgen and Staden.
Figures
Forward citations
Cited by 2 Pith papers
-
The semi-inducibility of the blue--blue--red path on four vertices
The maximum asymptotic density of semi-induced blue-blue-red paths on four vertices is p*, attained by a large clique together with an asymptotically regular component.
-
Semi-inducibility of 4-vertex graphs
The paper determines the semi-inducibility constants for all 4-vertex non-complete graphs except the blue-blue-red path, using flag algebra certificates and stability arguments.
Reference graph
Works this paper leans on
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.