\documentclass[11pt]{article}

\usepackage[a4paper,margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{booktabs}
\usepackage[hidelinks]{hyperref}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\R}{\mathbb{R}}
\newcommand{\one}{\mathbf{1}}
\newcommand{\tr}{\operatorname{Tr}}

\title{Off-Diagonal Commonality of a Shorter Even Cycle and a Longer Odd Cycle}
\author{Taeyoung Kim}
\date{\today}
\hypersetup{
  pdftitle={Off-Diagonal Commonality of a Shorter Even Cycle and a Longer Odd Cycle},
  pdfauthor={Taeyoung Kim},
  pdfsubject={The exact commonality region for a shorter even cycle and a longer odd cycle}
}

\begin{document}
\maketitle

\begin{abstract}
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}$.
\end{abstract}

\section{Definitions and main theorem}

A \emph{graphon} is a symmetric measurable function
$W\colon[0,1]^2\to[0,1]$.  If $H$ is a finite graph, its homomorphism density
in $W$ is
\[
  t(H,W)
  :=
  \int_{[0,1]^{V(H)}}
  \prod_{uv\in E(H)}W(x_u,x_v)
  \prod_{u\in V(H)}dx_u.
\]
We write $e(H)=|E(H)|$.  See Lov\'asz~\cite{Lovasz} for background on
graphons and homomorphism densities.

Following Behague, Morrison, and Noel~\cite{BMN}, let $a,b\in(0,1)$ with
$a+b=1$.  An ordered pair $(H_1,H_2)$ is \emph{$(a,b)$-common} if
\begin{equation}
  \frac{t(H_1,W)}{e(H_1)a^{e(H_1)-1}}
  +
  \frac{t(H_2,1-W)}{e(H_2)b^{e(H_2)-1}}
  \ge
  \frac{a}{e(H_1)}+\frac{b}{e(H_2)}
  \label{eq:common-definition}
\end{equation}
for every graphon $W$.  Define
\[
  \pi(H_1,H_2)
  :=
  \{a\in(0,1):(H_1,H_2)\text{ is }(a,1-a)\text{-common}\}.
\]
Taking $a=1/2$ and $H_1=H_2=H$ turns \eqref{eq:common-definition} into
$t(H,W)+t(H,1-W)\ge2^{1-e(H)}$, so $1/2\in\pi(H,H)$ says exactly that $H$ is
a common graph.

Our main result determines $\pi(C_n,C_\ell)$ when the shorter cycle is even
and the longer one is odd.

\begin{theorem}[Shorter even and longer odd cycles]
  \label{thm:main}
  Let $n\ge4$ be even and let $\ell>n$ be odd.  Then
  \[
    \pi(C_n,C_\ell)=\bigl(0,a_{n,\ell}^{\star}\bigr],
  \]
  where $a_{n,\ell}^{\star}$ is the unique solution in $(1/2,1)$ of
  \begin{equation}
    \frac{a^{n-1}\bigl(n+(\ell-n)a\bigr)}{\ell}
    =2^{1-n}.
    \label{eq:critical-main}
  \end{equation}
\end{theorem}

That \eqref{eq:critical-main} has exactly one root in $(1/2,1)$ is elementary,
since its left-hand side is strictly increasing in $a$; this is
Lemma~\ref{lem:critical-point}.  The content of Theorem~\ref{thm:main} is that
$\pi(C_n,C_\ell)$ is precisely the half-open interval cut out by that root:
commonality holds up to and including $a_{n,\ell}^{\star}$, and fails
immediately afterwards.

Table~\ref{tab:critical-values} gives some numerical values of the critical
point.  The columns give the even length $n$ and
the rows give the odd length $\ell$.  An entry is replaced by $0$ when
$n\ge\ell$, which lies outside the shorter-even regime of
Theorem~\ref{thm:main}.

\begin{table}[ht]
  \centering
  \begin{tabular}{c@{\qquad}cccccc}
    \toprule
    $\ell\backslash n$ & $4$ & $6$ & $8$ & $10$ & $12$ & $14$ \\
    \midrule
    $5$  & $0.517213\ldots$ & $0$ & $0$ & $0$ & $0$ & $0$ \\
    $7$  & $0.538147\ldots$ & $0.507351\ldots$ & $0$ & $0$ & $0$ & $0$ \\
    $9$  & $0.550283\ldots$ & $0.517832\ldots$ & $0.504065\ldots$ & $0$ & $0$ & $0$ \\
    $11$ & $0.558163\ldots$ & $0.524929\ldots$ & $0.510344\ldots$ & $0.502577\ldots$ & $0$ & $0$ \\
    $13$ & $0.563680\ldots$ & $0.530044\ldots$ & $0.514968\ldots$ & $0.506759\ldots$ & $0.501779\ldots$ & $0$ \\
    $15$ & $0.567753\ldots$ & $0.533903\ldots$ & $0.518513\ldots$ & $0.510006\ldots$ & $0.504764\ldots$ & $0.501302\ldots$ \\
    \bottomrule
  \end{tabular}
  \caption{The critical values $a_{n,\ell}^{\star}$ for shorter even cycles
  $C_n$ and longer odd cycles $C_\ell$.}
  \label{tab:critical-values}
\end{table}

The proof of Theorem~\ref{thm:main} is self-contained apart from standard
finite-dimensional spectral facts.

\section{Proof of the main theorem}

We begin with the scalar part of the proof, which establishes the existence
and uniqueness of $a_{n,\ell}^{\star}$ and the numerical bounds on the
quantities attached to $a$ that are used later.  From here to the end of the
section, let
\[
  n\ge4\text{ be even},
  \qquad
  \ell>n\text{ be odd},
  \qquad
  d:=\ell-n.
\]
Thus $d$ is a positive odd integer.  For $a\in(0,1)$, set $b:=1-a$ and
define
\begin{align}
  \kappa_{n,\ell}(a)
  &:=\frac{n a^{n-1}}{\ell b^{\ell-1}},\\
  \rho_{n,\ell}(a)
  &:=a^n+\frac n\ell a^{n-1}b
    =\frac{a^{n-1}(n+da)}{\ell}.
  \label{eq:rho-definition}
\end{align}
Note that $(C_n,C_\ell)$ is $(a,b)$-common if and only if
\begin{equation}
  t(C_n,W)+\kappa_{n,\ell}(a)t(C_\ell,1-W)
  \ge\rho_{n,\ell}(a)
  \label{eq:scaled-target}
\end{equation}
for every graphon $W$: this is \eqref{eq:common-definition} multiplied
through by $na^{n-1}$.

\begin{lemma}[The critical point]
  \label{lem:critical-point}
  The function $\rho_{n,\ell}$ is strictly increasing on $(0,1)$, and there is
  a unique $a_{n,\ell}^{\star}\in(1/2,1)$ such that
  \begin{equation}
    \rho_{n,\ell}(a_{n,\ell}^{\star})=2^{1-n}.
    \label{eq:critical-rho}
  \end{equation}
\end{lemma}

\begin{proof}
  Differentiating \eqref{eq:rho-definition} gives
  \[
    \rho_{n,\ell}'(a)
    =\frac{n}{\ell}a^{n-2}(n-1+da)>0.
  \]
  Hence $\rho_{n,\ell}$ is strictly increasing.  At the endpoints,
  \[
    \rho_{n,\ell}\left(\frac12\right)
    =2^{1-n}\frac{n+\ell}{2\ell}
    <2^{1-n},
    \qquad
    \rho_{n,\ell}(1)=1>2^{1-n}.
  \]
  The intermediate value theorem proves existence, and strict monotonicity
  proves uniqueness.
\end{proof}

The next lemma gives bounds on $\kappa_{n,\ell}(a)b^{d}$ and on $b$, with
constants not depending on $n$ or $\ell$.

\begin{lemma}[Critical coefficient bounds]
  Let
  \[
    a^\star:=a_{n,\ell}^{\star},
    \qquad b^\star:=1-a^\star,
    \qquad \kappa^\star:=\kappa_{n,\ell}(a^\star).
  \]
  Then
  \[
    \kappa^\star(b^\star)^d<1,
    \qquad
    b^\star>\frac5{14}.
  \]
  Consequently, for every $0<a\le a^\star$, with $b=1-a$ and
  $\kappa=\kappa_{n,\ell}(a)$,
  \begin{equation}
    \kappa b^d<1,
    \qquad
    b>\frac5{14}.
    \label{eq:all-kappa-bounds}
  \end{equation}
\end{lemma}

\begin{proof}
  Write
  \[
    a^\star=\frac{1+\delta}{2},
    \qquad
    b^\star=\frac{1-\delta}{2},
    \qquad
    \delta\in(0,1).
  \]
  Since $\ell=n+d$, the critical equation
  \eqref{eq:critical-rho} is equivalent to
  \begin{equation}
    (1+\delta)^{n-1}(\ell+n+d\delta)=2\ell.
    \label{eq:delta-critical}
  \end{equation}
  It follows that
  \[
    (1+\delta)^{n-1}
    <\frac{2\ell}{\ell+n}
    =1+\frac{d}{\ell+n}.
  \]
  Bernoulli's inequality gives $(1+\delta)^{n-1}\ge1+(n-1)\delta$, so
  $(n-1)\delta<d/(\ell+n)$ and hence
  \[
    0<\delta<\frac{d}{(n-1)(\ell+n)}.
  \]
  A second application of Bernoulli's inequality gives
  \[
    (1-\delta)^{n-1}
    \ge1-(n-1)\delta
    >1-\frac{d}{\ell+n}
    =\frac{2n}{\ell+n}.
  \]
  Combining these two estimates gives
  \begin{align*}
    \kappa^\star(b^\star)^d
    &=\frac n\ell
      \left(\frac{1+\delta}{1-\delta}\right)^{n-1}\\
    &<\frac n\ell
      \frac{2\ell/(\ell+n)}{2n/(\ell+n)}
    =1.
  \end{align*}

  Equation~\eqref{eq:delta-critical} also implies
  $(1+\delta)^{n-1}<2$.  Since $n-1\ge3$ and $1+\delta>1$,
  \[
    (1+\delta)^3\le(1+\delta)^{n-1}<2.
  \]
  If $\delta\ge2/7$, then
  \[
    (1+\delta)^3\ge\left(\frac97\right)^3
    =\frac{729}{343}>2,
  \]
  a contradiction.  Thus $\delta<2/7$, and hence
  \[
    b^\star=\frac{1-\delta}{2}>\frac5{14}.
  \]

  Finally,
  \[
    \kappa_{n,\ell}(a)(1-a)^d
    =\frac n\ell
      \left(\frac{a}{1-a}\right)^{n-1}
  \]
  is strictly increasing with respect to $a$ on $(0,1)$.  Therefore
  $\kappa b^d\le\kappa^\star(b^\star)^d<1$ whenever
  $a\le a^\star$.  Moreover,
  $b=1-a\ge1-a^\star=b^\star>5/14$.
\end{proof}

\begin{remark}
  The proof of Proposition~\ref{prop:lower-bound} uses the bound $b>5/14$
  only through the inequality $2b^2>1/4$.  Any explicit lower bound on $b$
  larger than $1/(2\sqrt2)=0.35355\ldots$ would therefore serve, and
  $5/14=0.35714\ldots$ is a convenient rational one.
\end{remark}

Turning to Theorem~\ref{thm:main} itself, we first show that it is enough to
prove the required inequalities for step graphons.  This allows us to assume
that the integral operator has finite rank and is represented by a real
symmetric matrix, so the eigenvalue arguments below do not require the
spectral theory of compact operators.

\begin{lemma}[Step-graphon reduction]
  \label{lem:step-reduction}
  Fix integers $n,\ell\ge3$ and a continuous function
  $\Phi\colon\R^2\to\R$.  Suppose that
  \[
    \Phi\bigl(t(C_n,W),t(C_\ell,1-W)\bigr)\ge0
  \]
  for every step graphon $W$.  Then the same inequality holds for
  every graphon $W$.
\end{lemma}

\begin{proof}
  For $j\ge1$, partition $[0,1]$ into its $2^j$ dyadic intervals of equal
  length, and let $\mathcal A_j$ be the finite sigma-algebra generated by this
  partition.  Set
  \[
    W_j:=\mathbb E[W\mid\mathcal A_j\otimes\mathcal A_j].
  \]
  Conditional expectation preserves symmetry and the pointwise bounds
  $0\le W\le1$, so $W_j$ is a step graphon.

  The dyadic rectangle step functions form nested subspaces whose union is
  dense in $L^2([0,1]^2)$.  Since conditional expectation is the orthogonal
  projection onto the corresponding subspace,
  \[
    \|W_j-W\|_2\longrightarrow0.
  \]
  The underlying space has measure one, so also
  $\|W_j-W\|_1\to0$.

  For every fixed $m\ge3$, the telescoping identity for products and the
  bounds $0\le W_j,W\le1$ give
  \[
    |t(C_m,W_j)-t(C_m,W)|
    \le m\|W_j-W\|_1.
  \]
  Indeed, after writing $x_{m+1}=x_1$, expand the difference of the two
  products into $m$ terms, with the $i$th term containing
  $(W_j-W)(x_i,x_{i+1})$ and all other factors bounded in absolute value by
  one.  Integration of each term gives $\|W_j-W\|_1$.  The same estimate
  applies to $1-W_j$ and $1-W$.  Both cycle densities therefore converge,
  and continuity of $\Phi$ proves the lemma.
\end{proof}

Let $K$ be a symmetric step kernel, constant on every rectangle
$B_i\times B_j$ of a finite measurable partition
\[
  [0,1]=B_1\sqcup\cdots\sqcup B_N,
  \qquad |B_i|>0.
\]
Let $T_K$ be its integral operator on $L^2([0,1])$,
\[
  (T_Kf)(x)=\int_0^1K(x,y)f(y)\,dy.
\]
Write $\one_S$ for the indicator function of a measurable set $S$, let
$\one:=\one_{[0,1]}$, and set
\[
  E:=\operatorname{span}\{\one_{B_1},\ldots,\one_{B_N}\}.
\]
The operator $T_K$ maps $L^2([0,1])$ into $E$ and vanishes on $E^\perp$, so
it is determined by its restriction $T_K|_E$.  In the orthonormal basis
\[
  e_i:=\frac{\one_{B_i}}{\sqrt{|B_i|}}
  \qquad(1\le i\le N)
\]
of $E$, that restriction is represented by the real symmetric matrix
\[
  \bigl(K_{ij}\sqrt{|B_i||B_j|}\bigr)_{i,j=1}^N,
\]
where $K_{ij}$ is the value of $K$ on $B_i\times B_j$.  We call such an $E$ a
step space \emph{associated with} $K$.  Two partitions on which $K$ is
constant admit a common refinement, and refining enlarges $E$ while appending
zero eigenvalues to the matrix above; hence the nonzero spectrum of $T_K|_E$
does not depend on which associated step space is chosen.

\begin{lemma}[Cycle densities are traces]
  \label{lem:trace-density}
  For every integer $m\ge3$,
  \[
    t(C_m,K)=\tr(T_K^m),
  \]
  where the trace is taken on $E$.
\end{lemma}

\begin{proof}
  Expanding the matrix trace in the basis $(e_i)_{i=1}^N$ gives
  \[
    \tr(T_K^m)
    =
    \sum_{i_1,\ldots,i_m=1}^N
    |B_{i_1}|\cdots|B_{i_m}|
    K_{i_1i_2}K_{i_2i_3}\cdots K_{i_mi_1}.
  \]
  This is precisely the step-function expansion of $t(C_m,K)$.
\end{proof}

Let $J:=T_1$ be the operator of the constant kernel $1$.  Since $[0,1]$ has
measure one, $Jf=\langle\one,f\rangle\one$, so $J$ is the rank-one orthogonal
projection onto the constant functions.  As $K\mapsto T_K$ is linear, a step
graphon $W$ and its complement $U:=1-W$ satisfy
\begin{equation}
  T_W=J-T_U.
  \label{eq:operator-complement}
\end{equation}

Combined with Lemma~\ref{lem:trace-density}, this expresses every cycle
density of $W$ as the trace of a power of $J-T_U$.  We now bound such traces
from below in terms of the eigenvalues of $T_U$ alone.

For a vector $x\in\R^N$, write $x^\downarrow$ for its coordinates rearranged
in nonincreasing order.  Recall that $x$ is \emph{majorised} by $y$, written
$x\prec y$, if
\[
  \sum_{i=1}^j x_i^\downarrow
  \le
  \sum_{i=1}^j y_i^\downarrow
  \quad(1\le j<N),
  \qquad
  \sum_{i=1}^N x_i=\sum_{i=1}^N y_i.
\]
Karamata's inequality~\cite[Chapter~4]{MOA} states that, whenever $x\prec y$ and
$\varphi\colon\R\to\R$ is convex,
\begin{equation}
  \sum_{i=1}^N\varphi(x_i)
  \le
  \sum_{i=1}^N\varphi(y_i).
  \label{eq:karamata}
\end{equation}

We need the following rank-one case of Lidskii's additive majorisation
theorem.  A proof is included for completeness.

\begin{lemma}[Rank-one lower majorisation]
  \label{lem:rank-one-majorisation}
  Let $A$ be a real symmetric $N\times N$ matrix with eigenvalues
  \[
    \alpha_1\ge\alpha_2\ge\cdots\ge\alpha_N,
  \]
  and let $P$ be a rank-one orthogonal projection.  If
  \[
    \mu_1\ge\mu_2\ge\cdots\ge\mu_N
  \]
  are the eigenvalues of $A+P$, then
  \[
    (\alpha_1,\ldots,\alpha_{N-1},\alpha_N+1)
    \prec
    (\mu_1,\ldots,\mu_N).
  \]
\end{lemma}

\begin{proof}
  We use the min--max formulation of the eigenvalues,
  \begin{equation}
    \alpha_i
    =\max_{\dim V=i}\ \min_{\substack{x\in V\\ \|x\|=1}}\langle x,Ax\rangle
    \qquad(1\le i\le N),
    \label{eq:min-max}
  \end{equation}
  where $V$ runs over the subspaces of $\R^N$ of dimension $i$; the same
  formula with $A+P$ in place of $A$ gives the $\mu_i$.  We first show that
  the two spectra interlace:
  \begin{equation}
    \mu_1\ge\alpha_1\ge\mu_2\ge\alpha_2\ge\cdots\ge\mu_N\ge\alpha_N.
    \label{eq:rank-one-interlacing}
  \end{equation}
  Equivalently, $\mu_i\ge\alpha_i$ for $1\le i\le N$ and
  $\alpha_i\ge\mu_{i+1}$ for $1\le i<N$.

  For the first family of inequalities, note that $P$ is positive
  semidefinite, so
  $\langle x,(A+P)x\rangle\ge\langle x,Ax\rangle$ for every unit vector $x$.
  Hence the inner minimum in \eqref{eq:min-max} can only increase when $A$ is
  replaced by $A+P$, and so can the maximum over $V$; therefore
  $\mu_i\ge\alpha_i$ for every $i\le N$.

  For the second family of inequalities, fix $1\le i<N$ and let $V$ be a
  subspace of dimension $i+1$.  The projection $P$ has rank one, so $\ker P$
  has dimension $N-1$, and $V+\ker P\subseteq\R^N$.  Hence
  \begin{align*}
    \dim(V\cap\ker P)
    &=\dim V+\dim\ker P-\dim(V+\ker P)\\
    &\ge(i+1)+(N-1)-N
    =i.
  \end{align*}
  Choose a subspace $V'\subseteq V\cap\ker P$ of dimension exactly $i$.
  Every $x\in\ker P$ satisfies $(A+P)x=Ax$, and minimising over the smaller
  space $V'$ can only increase the value, so
  \[
    \min_{\substack{x\in V\\ \|x\|=1}}\langle x,(A+P)x\rangle
    \le\min_{\substack{x\in V'\\ \|x\|=1}}\langle x,(A+P)x\rangle
    =\min_{\substack{x\in V'\\ \|x\|=1}}\langle x,Ax\rangle
    \le\alpha_i,
  \]
  where the last step is \eqref{eq:min-max} applied to the $i$-dimensional
  subspace $V'$.  Taking the maximum over all subspaces $V$ of dimension
  $i+1$ preserves the inequality, and by \eqref{eq:min-max} for $A+P$ that
  maximum is $\mu_{i+1}$.  Hence $\mu_{i+1}\le\alpha_i$, which proves
  \eqref{eq:rank-one-interlacing}.

  A rank-one orthogonal projection has trace one, so
  \begin{equation}
    \sum_{i=1}^N\mu_i=\tr(A+P)=\tr(A)+1=\sum_{i=1}^N\alpha_i+1,
    \label{eq:total-sum}
  \end{equation}
  which proves the equality of total sums required in the definition of
  majorisation.

  Let
  \[
    v:=(\alpha_1,\ldots,\alpha_{N-1},\alpha_N+1).
  \]
  Its coordinates also sum to $\sum_{i=1}^N\alpha_i+1$.  For the partial
  sums, fix $1\le j<N$.  The sum of the $j$ largest coordinates of $v$ is
  the maximum of $\sum_{i\in S}v_i$ over all $j$-element subsets
  $S\subseteq\{1,\ldots,N\}$.

  If $N\notin S$, then the bound is immediate:
  \[
    \sum_{i\in S}v_i
    \le\sum_{i=1}^j\alpha_i
    \le\sum_{i=1}^j\mu_i.
  \]
  If $N\in S$, we first have
  \[
    \sum_{i\in S}v_i
    \le1+\alpha_N+\sum_{i=1}^{j-1}\alpha_i.
  \]
  It remains to bound $\sum_{i=1}^j\mu_i$ from below by the same quantity.
  Applying $\mu_{i+1}\le\alpha_i$ from \eqref{eq:rank-one-interlacing} to
  $i=j,\ldots,N-1$ gives
  \[
    \sum_{i=j+1}^N\mu_i
    =\sum_{i=j}^{N-1}\mu_{i+1}
    \le\sum_{i=j}^{N-1}\alpha_i,
  \]
  so with \eqref{eq:total-sum},
  \begin{align*}
    \sum_{i=1}^j\mu_i
    &=\sum_{i=1}^N\mu_i-\sum_{i=j+1}^N\mu_i\\
    &\ge\Bigl(\sum_{i=1}^N\alpha_i+1\Bigr)-\sum_{i=j}^{N-1}\alpha_i
    =1+\alpha_N+\sum_{i=1}^{j-1}\alpha_i.
  \end{align*}
  This settles the case $N\in S$, so every partial-sum inequality in the
  definition of majorisation holds.
\end{proof}

\begin{corollary}[Even trace after subtracting a rank-one projection]
  \label{cor:rank-one-trace}
  Let $T$ be a real symmetric $N\times N$ matrix with eigenvalues
  \[
    \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_N,
  \]
  and let $P$ be a rank-one orthogonal projection.  If $m\ge2$ is even, then
  \[
    \tr\bigl((P-T)^m\bigr)
    \ge
    (1-\lambda_1)^m+
    \sum_{i=2}^N|\lambda_i|^m.
  \]
\end{corollary}

\begin{proof}
  Apply Lemma~\ref{lem:rank-one-majorisation} to $A=-T$.  The eigenvalues of
  $-T$ in nonincreasing order are
  \[
    -\lambda_N\ge\cdots\ge-\lambda_1.
  \]
  Writing $\mu_1\ge\cdots\ge\mu_N$ for the eigenvalues of $P-T$, the lemma
  gives
  \[
    (-\lambda_N,\ldots,-\lambda_2,1-\lambda_1)
    \prec(\mu_1,\ldots,\mu_N).
  \]
  Applying Karamata's inequality to the convex function $x\mapsto x^m$ and
  using $(-\lambda_i)^m=|\lambda_i|^m$, which holds because $m$ is even,
  gives the result.
\end{proof}

The pointwise bounds $0\le U\le1$ enter the argument through the following
consequences for the spectrum of $T_U$.

\begin{lemma}[Perron domination and the tail bound]
  Let $U$ be a step graphon and let $T=T_U|_E$ be its matrix on an
  associated step-function space.  If
  \[
    \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_N
  \]
  are the eigenvalues of $T$, then
  \begin{align}
    &0\le\lambda_1\le1,
    \label{eq:lambda-one-range}\\
    &|\lambda_i|\le\lambda_1
    \quad(1\le i\le N),
    \label{eq:perron-domination}\\
    &\sum_{i=2}^N\lambda_i^2
    \le\lambda_1(1-\lambda_1)
    \le\frac14.
    \label{eq:tail-bound}
  \end{align}
\end{lemma}

\begin{proof}
  Let $f\in E$ be a unit vector.  Then $|f|\in E$ is also a unit vector, so
  $\langle|f|,T|f|\rangle\le\lambda_1$.  Pointwise nonnegativity of $U$
  gives $|\langle f,Tf\rangle|\le\langle|f|,T|f|\rangle$, and $U\le1$ gives
  \[
    \langle|f|,T|f|\rangle
    \le\left(\int_0^1|f|\right)^2
    \le\|f\|_2^2=1 .
  \]

  Taking $f$ to be a unit eigenvector of $\lambda_1$,
  \[
    \lambda_1=\langle f,Tf\rangle
    \le|\langle f,Tf\rangle|
    \le\langle|f|,T|f|\rangle
    \le1 .
  \]
  For an arbitrary unit vector $f$,
  \[
    \lambda_1\ge\langle|f|,T|f|\rangle\ge|\langle f,Tf\rangle|\ge0 .
  \]
  Moreover, taking $f$ to be a unit eigenvector of $\lambda_i$,
  \[
    |\lambda_i|=|\langle f,Tf\rangle|\le\langle|f|,T|f|\rangle\le\lambda_1 .
  \]

  Finally, let
  \[
    p:=\int_{[0,1]^2}U(x,y)\,dx\,dy
    =\langle\one,T\one\rangle ,
  \]
  which gives $p\le\lambda_1$.  Since $U^2\le U$,
  \[
    \sum_{i=1}^N\lambda_i^2
    =\tr(T^2)
    =\int_{[0,1]^2}U(x,y)^2\,dx\,dy
    \le p.
  \]
  Therefore
  \[
    \sum_{i=2}^N\lambda_i^2
    \le p-\lambda_1^2
    \le\lambda_1-\lambda_1^2
    \le\frac14.
  \]
\end{proof}

We can now assemble the proof.

\begin{proposition}[Spectral reduction]
  \label{prop:spectral-reduction}
  Let $W$ be a step graphon, set $U=1-W$, and let
  $T=T_U|_E$ on an associated step-function space.  Order the eigenvalues of
  $T$ as
  \[
    \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_N.
  \]
  For every $\kappa>0$,
  \begin{equation}
    t(C_n,W)+\kappa t(C_\ell,U)
    \ge
    f_\kappa(\lambda_1)
    +\sum_{i=2}^N
      \lambda_i^n(1+\kappa\lambda_i^d),
    \label{eq:master-spectral}
  \end{equation}
  where
  \[
    f_\kappa(x):=(1-x)^n+\kappa x^\ell,
    \qquad 0\le x\le1.
  \]
\end{proposition}

\begin{proof}
  Let $P:=J|_E$.  Since $\one\in E$ and $\|\one\|_2=1$, $P$ is a rank-one
  orthogonal projection.  By \eqref{eq:operator-complement},
  $T_W|_E=P-T$.  Lemma~\ref{lem:trace-density} and
  Corollary~\ref{cor:rank-one-trace} give
  \[
    t(C_n,W)
    =\tr\bigl((P-T)^n\bigr)
    \ge(1-\lambda_1)^n+
      \sum_{i=2}^N|\lambda_i|^n.
  \]
  Because $n$ is even, $|\lambda_i|^n=\lambda_i^n$.  This inequality together
  with
  \[
    t(C_\ell,U)=\tr(T^\ell)=\sum_{i=1}^N\lambda_i^\ell
  \]
  gives \eqref{eq:master-spectral}.
\end{proof}

\begin{proposition}[Lower bound up to the critical point]
  \label{prop:lower-bound}
  If $0<a\le a_{n,\ell}^{\star}$, then every graphon $W$ satisfies
  \begin{equation}
    t(C_n,W)+\kappa_{n,\ell}(a)t(C_\ell,1-W)
    \ge\rho_{n,\ell}(a).
    \label{eq:lower-bound}
  \end{equation}
\end{proposition}

\begin{proof}
  By Lemma~\ref{lem:step-reduction} we may assume that $W$ is a step
  graphon.  Let $U=1-W$, let $T=T_U|_E$, and write the eigenvalues of $T$ as
  \[
    \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_N.
  \]
  Proposition~\ref{prop:spectral-reduction}, applied with
  $\kappa:=\kappa_{n,\ell}(a)$, gives
  \begin{equation}
    t(C_n,W)+\kappa t(C_\ell,U)
    \ge f_\kappa(\lambda_1)
      +\sum_{i=2}^N\lambda_i^n(1+\kappa\lambda_i^d).
    \label{eq:lower-start}
  \end{equation}

  Suppose first that $1+\kappa\lambda_i^d\ge0$ for every $i\ge2$.  Then every
  summand of the sum in \eqref{eq:lower-start} is nonnegative, since $n$ is
  even, and it is enough to bound $f_\kappa(\lambda_1)$ from below.  Write
  $b:=1-a$.  Since $\kappa=\kappa_{n,\ell}(a)$,
  \begin{align*}
    f_\kappa'(x)
    &=-n(1-x)^{n-1}+\kappa\ell x^{\ell-1},\\
    f_\kappa''(x)
    &=n(n-1)(1-x)^{n-2}
      +\kappa\ell(\ell-1)x^{\ell-2}>0,
  \end{align*}
  and
  \[
    f_\kappa'(b)
    =-na^{n-1}+\kappa\ell b^{\ell-1}=0.
  \]
  Thus $f_\kappa$ is strictly convex and has its unique minimum at $b$, with
  \[
    f_\kappa(b)
    =a^n+\kappa b^\ell
    =\rho_{n,\ell}(a).
  \]
  By \eqref{eq:lambda-one-range} the value $\lambda_1$ lies in the domain
  $[0,1]$ of $f_\kappa$, so \eqref{eq:lower-start} gives
  \[
    t(C_n,W)+\kappa t(C_\ell,U)
    \ge f_\kappa(\lambda_1)
    \ge f_\kappa(b)
    =\rho_{n,\ell}(a).
  \]

  Call an eigenvalue $\lambda_i$, $i\ge2$, \emph{dangerous} if
  \[
    1+\kappa\lambda_i^d<0,
  \]
  that is, if its summand in \eqref{eq:lower-start} is negative.  As shown
  above, if there is no dangerous eigenvalue then the claim follows.  Assume
  therefore that there is at least one.  Since $d$ is odd and $\kappa>0$, a
  dangerous eigenvalue has the form $\lambda_i=-\beta$ with $\beta>0$.  The
  bound $\kappa b^d<1$ of \eqref{eq:all-kappa-bounds} with the definition of
  a dangerous eigenvalue gives
  \[
    \kappa\beta^d>1>\kappa b^d,
  \]
  and since $x\mapsto x^d$ is strictly increasing, this yields
  \begin{equation}
    \beta>b>\frac5{14},
    \label{eq:dangerous-magnitude}
  \end{equation}
  where the second inequality is the second bound of
  \eqref{eq:all-kappa-bounds}.

  We now show that there can be at most one dangerous eigenvalue.  If two of
  $\lambda_2,\ldots,\lambda_N$ were dangerous, with magnitudes $\beta$ and
  $\gamma$, then \eqref{eq:tail-bound} and \eqref{eq:dangerous-magnitude}
  would give a contradiction:
  \[
    \frac14
    \ge\sum_{i=2}^N\lambda_i^2
    \ge\beta^2+\gamma^2
    >2\left(\frac5{14}\right)^2
    =\frac{25}{98}
    >\frac14.
  \]

  So let the unique dangerous eigenvalue be $-\beta$.  Recall that
  \eqref{eq:dangerous-magnitude}, \eqref{eq:perron-domination} and
  \eqref{eq:lambda-one-range} give
  \[
    b<\beta\le\lambda_1\le1 .
  \]
  The strictly convex function $f_\kappa$ is increasing on $[b,1]$, so
  $f_\kappa(\lambda_1)\ge f_\kappa(\beta)$.  Since no other eigenvalue is
  dangerous, every summand of \eqref{eq:lower-start} apart from that of
  $-\beta$ is nonnegative, and therefore
  \begin{align*}
    t(C_n,W)+\kappa t(C_\ell,U)
    &\ge f_\kappa(\lambda_1)+\beta^n(1-\kappa\beta^d)\\
    &\ge f_\kappa(\beta)+\beta^n(1-\kappa\beta^d)\\
    &=(1-\beta)^n+\kappa\beta^\ell
      +\beta^n-\kappa\beta^{n+d}\\
    &=(1-\beta)^n+\beta^n\\
    &\ge2^{1-n},
  \end{align*}
  where the last inequality follows from convexity of $x\mapsto x^n$ applied
  to $\beta$ and $1-\beta$.  Finally, strict monotonicity of $\rho_{n,\ell}$ in 
  Lemma~\ref{lem:critical-point} and $a\le a_{n,\ell}^{\star}$ imply
  \[
    \rho_{n,\ell}(a)
    \le\rho_{n,\ell}(a_{n,\ell}^{\star})
    =2^{1-n}.
  \]
  This proves \eqref{eq:lower-bound} in the remaining case.
\end{proof}

The matching obstruction is the balanced disjoint union of two cliques,
\[
  W_{\mathrm{cl}}(x,y)
  :=
  \begin{cases}
    1,&x,y\in[0,1/2]
       \text{ or }x,y\in(1/2,1],\\
    0,&\text{otherwise}.
  \end{cases}
\]

\begin{proposition}[Two-clique obstruction]
  \label{prop:obstruction}
  If $a>a_{n,\ell}^{\star}$, then $W_{\mathrm{cl}}$ violates
  \eqref{eq:scaled-target}.
\end{proposition}

\begin{proof}
  Every homomorphism from the connected graph $C_n$ into $W_{\mathrm{cl}}$
  maps all vertices into one of the two halves, so
  \begin{equation}
    t(C_n,W_{\mathrm{cl}})
    =2\left(\frac12\right)^n
    =2^{1-n}.
    \label{eq:two-clique-density}
  \end{equation}
  The complement $1-W_{\mathrm{cl}}$ is the balanced complete bipartite
  graphon, and $\ell$ is odd, so
  \begin{equation}
    t(C_\ell,1-W_{\mathrm{cl}})=0.
    \label{eq:odd-bipartite-zero}
  \end{equation}
  By \eqref{eq:two-clique-density} and \eqref{eq:odd-bipartite-zero}, the
  left-hand side of \eqref{eq:scaled-target} at $W_{\mathrm{cl}}$ equals
  $2^{1-n}$.  Strict monotonicity of $\rho_{n,\ell}$
  (Lemma~\ref{lem:critical-point}) and $a>a_{n,\ell}^{\star}$ give
  \[
    \rho_{n,\ell}(a)
    >\rho_{n,\ell}(a_{n,\ell}^{\star})
    =2^{1-n},
  \]
  so \eqref{eq:scaled-target} fails at $W_{\mathrm{cl}}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
  By \eqref{eq:rho-definition} the left-hand side of the critical equation
  \eqref{eq:critical-main} is $\rho_{n,\ell}(a)$, so that equation is
  \eqref{eq:critical-rho}; Lemma~\ref{lem:critical-point} shows that it has a
  unique solution $a_{n,\ell}^{\star}$ in $(1/2,1)$, which is the number
  named in the theorem.

  Now fix $a\in(0,1)$.  By \eqref{eq:scaled-target}, $a$ belongs to
  $\pi(C_n,C_\ell)$ if and only if
  \[
    t(C_n,W)+\kappa_{n,\ell}(a)t(C_\ell,1-W)\ge\rho_{n,\ell}(a)
  \]
  holds for every graphon $W$.  If $a\le a_{n,\ell}^{\star}$, then
  Proposition~\ref{prop:lower-bound} establishes this inequality, so
  $a\in\pi(C_n,C_\ell)$.  If $a>a_{n,\ell}^{\star}$, then the two-clique
  graphon $W_{\mathrm{cl}}$ of Proposition~\ref{prop:obstruction} violates
  it, so $a\notin\pi(C_n,C_\ell)$.  The region therefore consists of exactly
  those $a$ with $0<a\le a_{n,\ell}^{\star}$, that is,
  \[
    \pi(C_n,C_\ell)=\bigl(0,a_{n,\ell}^{\star}\bigr].
    \qedhere
  \]
\end{proof}

\section{Remarks}

The proof of Theorem~\ref{thm:main} has been verified in the Lean~4
proof assistant~\cite{Lean4}, on top of the mathlib
library~\cite{mathlib}; see \url{https://github.com/mekty2012/Off-diagonal-Commonality-of-Even-and-Odd-Cycles}.  The
formal statement covers both directions and the existence and
uniqueness of $a_{n,\ell}^{\star}$: the inequality holds for every graphon
if and only if $a\le a_{n,\ell}^{\star}$.  The formal proof differs from
the one given here in four ways.

First, instead of the dyadic conditional expectations in
Lemma~\ref{lem:step-reduction}, the formal proof approximates $W$
directly by a step graphon in the $L^1$ norm; both cycle densities
are Lipschitz in that norm, so the inequality transfers.

Second, the interlacing inequalities \eqref{eq:rank-one-interlacing}
are proved by an intersection argument instead of the min--max
formulation: two spans of eigenvectors whose
dimensions add up to more than $N$ contain a common unit vector, and
evaluating the quadratic forms of $A$ and $A+P$ at that vector gives
the inequality.

Third, the rearrangement in Lemma~\ref{lem:rank-one-majorisation} is
not obtained by sorting.  Since the $\alpha_i$ are already ordered,
rearranging $(\alpha_1,\ldots,\alpha_{N-1},\alpha_N+1)$ only moves
the entry $\alpha_N+1$ to its correct position, and the formal proof
writes this down explicitly, with the partial sums in closed form.
Karamata's inequality \eqref{eq:karamata} is proved in a form that
requires only one of the two sequences to be monotone, so no second
sorting argument is needed.

Fourth, the derivatives of $f_\kappa$ are not computed.  The paper
locates the minimum of $f_\kappa$ at $b$ through $f_\kappa'$ and
$f_\kappa''$; the formal proof instead bounds $(1-x)^n$ and
$\kappa x^\ell$ from below by their supporting lines at $x=b$, both
instances of Bernoulli's inequality, and the sum of the two lines is
the constant $\rho_{n,\ell}(a)$ because
$\kappa\ell b^{\ell-1}=na^{n-1}$.  The same supporting-line estimate,
together with monotonicity of powers on the nonnegative reals, proves
that $f_\kappa$ is increasing on $[b,1]$.  Strict monotonicity of
$\rho_{n,\ell}$ is proved directly from its explicit formula, without
differentiating.  Finally, the formal proof obtains
$x^n+(1-x)^n\ge 2^{1-n}$ by applying the supporting-line inequality
at $1/2$ to both terms.
\begin{thebibliography}{9}

\bibitem{BMN}
N. Behague, N. Morrison, and J. A. Noel,
\emph{Common pairs of graphs},
Combin. Probab. Comput. \textbf{34} (2025), no.~5, 649--670;
\texttt{arXiv:2208.02045}.

\bibitem{Lovasz}
L. Lov\'asz,
\emph{Large Networks and Graph Limits},
American Mathematical Society Colloquium Publications, vol.~60,
American Mathematical Society, Providence, RI, 2012.

\bibitem{MOA}
A. W. Marshall, I. Olkin, and B. C. Arnold,
\emph{Inequalities: Theory of Majorization and Its Applications},
second edition, Springer Series in Statistics,
Springer, New York, 2011.

\bibitem{mathlib}
The mathlib Community,
\emph{The Lean mathematical library},
Proceedings of the 9th ACM SIGPLAN International Conference on
Certified Programs and Proofs (CPP 2020), ACM, 2020, pp.~367--381.

\bibitem{Lean4}
L. de Moura and S. Ullrich,
\emph{The Lean 4 theorem prover and programming language},
Automated Deduction -- CADE 28, Lecture Notes in Computer Science,
vol.~12699, Springer, 2021, pp.~625--635.

\end{thebibliography}

\end{document}