\section{\texorpdfstring{Upper bounds from alternating paths for general $\ell$}{Upper bounds from alternating paths for general ell}}
\label{sec:general-path-packing}

In this section and the next two sections, $\ell\ge5$. The argument
uses a matching that minimizes the polynomial weight order of
Cs\'oka and Pongr\'acz~\cite{CP}, followed by a second matching
obtained by exchanging edges along disjoint alternating paths.
The formal edge weights are
\[
 w_1(\varepsilon)=0,\qquad
 w_t(\varepsilon)=\sum_{j=0}^{t-2}2^{t-2-j}\varepsilon^j
 \quad(2\le t\le\ell).
\]
Coefficients are compared starting at the constant term. The
\emph{primary weight} is the constant coefficient, so its values
are $0,1,2,4,\ldots,2^{\ell-2}$. Fix a matching $\M_0$ of size $M$
that minimizes this order. Let $X_t$ be the set of endpoints of its
label-$t$ edges, and write $x_t=|X_t|/(2M)$, so $\sum_t x_t=1$.
Put
\[
 k=2^{\ell-2},\qquad S=3k-2\ell+4,\qquad
 c_1=c_\ell=1,\quad c_2=k,\quad
 c_t=2^{\ell-t+1}-2\ (3\le t<\ell).
\]
Here and below, an endpoint mass is divided by $M$, whereas an edge
count is divided by $M^2$. Thus $x_t$ is also the number of label-$t$
matching edges divided by $M$. Write $C_0=C_\lambda(\M_0)/M^2$.
No critical edge joins a covered vertex to an uncovered vertex:
replacing the incident matching edge by such an edge would decrease
the primary weight. Between distinct classes $X_i,X_j$, the
complementary-pair argument of Section~\ref{sec:foundations} gives
at most $2x_ix_jM^2$ critical edges. Denote the difference between
this upper bound and the actual count, divided by $M^2$, by
$e_{ij}\ge0$. Put $x=x_2$ and
\[
 Q=\sum_{t=1}^{\ell}\frac{(x_t-c_t/S)^2}{c_t}.
\]
Color the matching edges inside $X_2$ red and its label-1 edges blue.
An alternating path alternates red and blue edges; it is
\emph{red-ended} if its first and last edges are red. There is no
alternating cycle, and no red-ended alternating path with $k$ blue
edges, since either would give a matching of smaller primary weight.
We use the following consequence of the alternating-path lemma
of~\cite{CP}: a graph on $v$ disjoint red pairs with no
alternating cycle and no red-ended alternating path containing $b$
blue edges has at most $(1-1/b)v^2+O_b(v)$ blue edges. When the
forbidden number $k$ is even, the peeling proof also partitions the
red pairs into $p=k/2$ layers. After deleting $O_\ell(M)$ blue
edges, each pair in layer $i$ can be oriented as $L_iR_i$ so that
all remaining blue edges belong to left--left pairs or to $L_iR_j$
with $i<j$. The mass $a_i$ of layer $i$ is its number of red pairs
divided by $M$; hence $\sum_i a_i=x$. This set of permitted pairs is
the \emph{blue template}. Let $E$ be the number of its missing blue
edges divided by $M^2$, and put
\[
 R=\frac12\sum_{i=1}^{p}(a_i-2x/k)^2.
\]
The cross-class bounds just described give
$2x_ix_j$ for each $i<j$. The internal critical count in class $t$ is
at most $(1-1/c_t)x_t^2+o_\ell(1)$, by the alternating-path bound
of~\cite{CP}; for $t=1,\ell$ it is zero. The actual
$X_2$ template has density
\[
 x^2-\frac12\sum_i a_i^2=x^2-x^2/k-R,
\]
so its missing blue density gives the further loss $E$. Since
$\sum_t c_t=S$ and $\sum_t x_t=1$, completing squares gives
$\sum_t x_t^2/c_t=1/S+Q$.
Combining these estimates gives a nonnegative deficit $D$ such that
\begin{equation}\label{eq:general-deficit}
 C_0\le 1-\frac1S-D+o_\ell(1),\qquad
 Q+R+E+\sum_{i<j}e_{ij}\le D+o_\ell(1).
\end{equation}
One can make $D$ literally nonnegative at finite $M$ by adding a fixed
$O_\ell(1/M)$ allowance to its definition. Every error below involves
only the original $2M$ covered vertices and is independent of $N$.

\subsection{A constraint from a maximal collection of disjoint paths}
Choose an integer $b$ with $k/2\le b<k$, and put $L=b+1$.
Pack vertex-disjoint red-ended alternating paths in $X_2$, each with
$b$ blue edges and $L$ original red edges, until no further path can be
added. Let $\mu$ be the mass of original red edges in this packing.
There are $\mu M/L$ paths, up to rounding.

The graph on the remaining $(x-\mu)M$ red pairs has no alternating cycle
and no alternating path with $b$ blue edges. Lemma~2.6 of
Cs\'oka--Pongr\'acz therefore bounds its blue density by
$(1-1/b)(x-\mu)^2+o_\ell(1)$. If $a_i'$ are the remaining layer masses,
the template gives the lower bound
\[
 (x-\mu)^2-\frac12\sum_i(a_i')^2-E-o_\ell(1).
\]
Since $0\le a_i'\le a_i$ and
$\frac12\sum_i a_i^2=x^2/k+R$, we obtain
\begin{equation}\label{eq:general-path-resource}
 R+E\ge\frac{(x-\mu)^2}{b}-\frac{x^2}{k}-o_\ell(1).
\end{equation}
The mass constraint in $Q$ implies
\[
 Q\ge\frac{S}{k(S-k)}(x-k/S)^2.
\]
Minimizing the sum of this quadratic and the right side of
\eqref{eq:general-path-resource} over $x\in\mathbb R$ proves
\begin{equation}\label{eq:general-dmu}
 D\ge d_b(\mu)-o_\ell(1),\qquad
 d_b(\mu)=
 \frac{(k-b)/S-2\mu+\mu^2}{S-k+b}
 =\frac{(1-\mu)^2}{S-k+b}-\frac1S.
\end{equation}
The unconstrained minimizer is
$x=[b+(S-k)\mu]/(S-k+b)$; in particular this minimization is just
completion of a square.

\subsection{Constructing the comparison matching}
The closing edge of each packed path has label $\ell$. Indeed, if its
label were smaller, replacing the $L>k/2$ red edges by the $b$ blue
edges and the closing edge would lower primary cost from $L$ to at
most $k/2$. Exactly the same argument proves that \emph{each endpoint
has label $\ell$ to every originally uncovered vertex}: close the path
to that vertex instead, leaving its other endpoint uncovered. Matching
cardinality is unchanged in this switch.

Replace each path by its blue edges and its label-$\ell$ closing edge.
All path-internal vertices now have matching label 1; its two endpoints
have label $\ell$. We call these changes a demotion and a promotion,
respectively. Every promoted endpoint has only label-$\ell$ edges
to originally uncovered vertices, as just proved. No new outward
critical edge is therefore created. This conclusion holds for
arbitrary $N\ge2M$ and does not require the comparison matching to
minimize primary weight.

Every original red pair has one original left endpoint. Among the
$\mu M$ left endpoints of packed pairs, at most $2\mu M/L$ are path
endpoints. Thus at least $(1-2/L)\mu M$ original left vertices are
demoted to label 1. Their blue pairs become noncritical, giving a loss
of at least
\[
 \frac12(1-2/L)^2\mu^2M^2-EM^2-O_\ell(M).
\]
Only the $2\mu M/L$ promoted endpoints can create new critical pairs.
There are at most $4\mu M^2/L$ such pairs with original covered
vertices, and none with original uncovered vertices. Hence
\[
 C_{\rm path}-C_0
 \le E+\frac{4\mu}{L}-\frac12(1-2/L)^2\mu^2+o_\ell(1).
\]
The $E$ allowance is already present in $D$, so
\begin{equation}\label{eq:general-hmu}
 C_{\rm path}\le1-\frac1S-h_b(\mu)+o_\ell(1),\qquad
 h_b(\mu)=\frac12(1-2/L)^2\mu^2-\frac{4\mu}{L}.
\end{equation}
We may stop the packing at any smaller prescribed mass, with an
$O_\ell(1/M)$ rounding error.

\begin{theorem}\label{thm:general-path-bound}
For every integer $b$ with $k/2\le b<k$ and every $0<u<1$,
\[
 \gamma(\ell)\le
 \frac12-\frac1{2S}
 -\frac12\min\{d_b(u),h_b(u)\}.
\]
In particular one may maximize the last minimum over $u$ and over the
allowed integers $b$, and combine this with any other valid bound.
\end{theorem}
\begin{proof}
If $D\ge d_b(u)-o_\ell(1)$, use the original matching. Otherwise,
\eqref{eq:general-dmu} and the strict decrease of $d_b$ on $[0,1)$
force the maximal path packing to cover at least mass $u-o_\ell(1)$.
Stop at that mass and use \eqref{eq:general-hmu}. Dividing the count
bound by $2$ proves the assertion. Strict inequalities can first be
used with an arbitrarily small fixed margin, followed by passage to
the limit, so boundary cases are included.
\end{proof}

\subsection{Exact optimization and asymptotics}
Set $b=k/2$, $L=k/2+1$, $T=2S-k$, and
\[
 A=\frac12(1-2/L)^2-\frac2T,\quad
 B=\frac4T-\frac4L,\quad d_0=\frac{k}{ST}.
\]
Whenever $A>0$, the positive solution of $h_b(u)=d_b(u)$ is
\begin{equation}\label{eq:general-optimum-root}
 u_* =\frac{-B+\sqrt{B^2+4Ad_0}}{2A},\qquad
 \delta_k=\frac{k/S-4u_*+2u_*^2}{T}.
\end{equation}
If $0<u_*<1$ and $\delta_k>0$, this is the optimum of the one-variable
comparison: $d_b$ is decreasing, while $h_b$ is increasing on its
positive branch. Therefore
\begin{equation}\label{eq:general-explicit-radical}
 \gamma(\ell)\le\frac12-\frac1{2S}-\frac{\delta_k}{2}.
\end{equation}
The hypotheses hold for every $\ell\ge10$. Indeed $k\ge256$ and
$L\ge129$, so the positive zero
$8L/(L-2)^2$ of $h_b$ is less than $1/12$, whereas
$d_b(1/12)>0$ follows from $k/S>1/3$.
Also $A>0$, since
$A\ge\tfrac12(127/129)^2-1/384>0$.
Therefore the decreasing curve $d_b$ meets the positive increasing
branch of $h_b$ before the positive zero of $d_b$.

This choice of path length is optimal within the whole family of
Theorem~\ref{thm:general-path-bound} when $\ell\ge10$, not merely
within the $\mu$ optimization. To prove this, temporarily allow real
$b\in[k/2,k)$ and put $T_b=S-k+b$, $L=b+1$, and $a=1-2/L$.
At any positive intersection $h_b(u)=d_b(u)>0$, we have
$h_u=a^2u-4/L>a^2u/2$ and $d_u=-2(1-u)/T_b<0$.
The intersection value is strictly decreasing with $b$ if
\[
 (1-u)h_u>(4au^2+8u)T_b/L^2.
\]
This follows by implicit differentiation, using
$\partial_b d_b=-(1-u)^2/T_b^2$ and
$\partial_b h_b=(2au^2+4u)/L^2$.
For $\ell\ge10$, $S\ge14k/5$; positivity of $d_b(u)$ then gives
$(1-u)^2>23/28>81/100$, so $u<1/10$.
Since $a\ge127/129$ and $T_b/L^2\le12/k$, the left side is greater
than
\[
 \frac9{20}(127/129)^2u,
\]
while the right side is at most
$(42/5)(12/256)u=(63/160)u$.
The former constant is strictly larger. This proves monotonicity on
every positive branch. A nonpositive comparison cannot improve a
positive one, so the best allowed integer path length is $b=k/2$.
The rational comparisons and root brackets are also verified by
\path{general-certificate/verify_general.py}.

As $\ell\to\infty$, we have $S=3k+O(\log k)$,
$A=1/2+O(k^{-1})$, $B=O(k^{-1})$, and
$d_0=1/(15k)+O((\log k)/k^2)$. Thus
\[
 u_* =\sqrt{\frac{2}{15k}}+O(k^{-1}),\qquad
 \delta_k=\frac{k}{S(2S-k)}+O(k^{-3/2}).
\]
Combining the two principal terms in
\eqref{eq:general-explicit-radical} gives
\begin{equation}\label{eq:general-asymptotic}
 \boxed{\gamma(\ell)\le
 \frac12-\frac1{2S-k}+O(k^{-3/2})
 =\frac12-\frac1{5k}+O(k^{-3/2}).}
\end{equation}
The leading gap in the upper bound of~\cite{CP} is $1/(6k)$, whereas
the leading gap in \eqref{eq:general-asymptotic} is $1/(5k)$, larger
by a factor $6/5$. The treatment of uncovered vertices follows from
the label restriction proved for path endpoints, and is therefore
uniform in the number of such vertices.