Taeyoung Kim

math.CO — Combinatorics

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

Contributed by Taeyoung Kim

Let $n\ge4$ be even and let $\ell>n$ be odd. We determine the complete off-diagonal commonality region of the ordered pair $(C_n,C_\ell)$: it is the half-open interval $(0,a_{n,\ell}^{\star}]$ cut out by the unique root $a_{n,\ell}^{\star}\in(1/2,1)$ of $\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 $x^{n}+(1-x)^{n}\ge2^{1-n}$.