HEXAGONbeta

Off-Diagonal Commonality of a Shorter Even Cycle and a Longer Odd Cycle

Primarily AI-generated textHuman understanding: all partsmath.CO — Combinatorics

Contributed by Taeyoung Kim ↗

Version 1 / Nov 04, 2026 / CC BY 4.0

Abstract

Let n≥4n\ge4 be even and let ℓ>n\ell>n be odd. We determine the complete off-diagonal commonality region of the ordered pair (Cn,Cℓ)(C_n,C_\ell): it is the half-open interval (0,an,ℓ⋆](0,a_{n,\ell}^{\star}] cut out by the unique root an,ℓ⋆∈(1/2,1)a_{n,\ell}^{\star}\in(1/2,1) of an−1(n+(ℓ−n)a)ℓ=21−n.\frac{a^{n-1}\bigl(n+(\ell-n)a\bigr)}{\ell}=2^{1-n}. The upper endpoint is witnessed by the balanced disjoint union of two cliques. For the lower bound, cycle densities are expressed as traces of graphon operators. Rank-one eigenvalue majorisation separates the Perron eigenvalue from the rest of the spectrum, while the Hilbert--Schmidt norm leaves room for at most one negative eigenvalue to contribute with the wrong sign. That eigenvalue is paid for by the Perron eigenvalue, leaving the elementary inequality xn+(1−x)n≥21−nx^{n}+(1-x)^{n}\ge2^{1-n}.

Provenance statement

The proof was obtained by one-shot by ChatGPT 5.5 Pro with specific proof direction included in the prompt.

Tools used

OpenAI
ChatGPTVersion 5.5 Pro

References

  1. N. Behague, N. Morrison, and J. A. Noel, Common pairs of graphs , Combin. Probab. Comput. 34 (2025), no. 5, 649--670; arXiv:2208.02045 .arXiv
  2. L. Lovász, Large Networks and Graph Limits , American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012.
  3. A. W. Marshall, I. Olkin, and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications , second edition, Springer Series in Statistics, Springer, New York, 2011.
  4. The mathlib Community, The Lean mathematical library , Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, pp. 367--381.
  5. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , Automated Deduction -- CADE 28, Lecture Notes in Computer Science, vol. 12699, Springer, 2021, pp. 625--635.

Version history

  1. v1Submitted by Taeyoung KimInitial depositCurrentNov 03, 2026