\section{A lower bound for every number of labels}
\label{sec:general-lower}

The following construction extends the four-part labeling of
Cs\'oka and Pongr\'acz~\cite{CP}, which gives the lower bound $5/12$
for four labels. Its advantage is that the minimum over all perfect
matchings can be calculated exactly for every number of labels.

\begin{theorem}\label{thm:general-lower}
For every integer $\ell\ge2$,
\[
 \gamma(\ell)\ge\gamma'(\ell)\ge
 \frac12-\frac1{4(\ell-1)}.
\]
In particular these lower bounds tend to $1/2$ as $\ell\to\infty$.
\end{theorem}

Put $m=\ell-1$. The construction has parts
$A_1,\ldots,A_m,R$ with vertex proportions
\begin{equation}\label{eq:general-lower-masses}
 a_1=\frac1{4m},\qquad
 a_i=\frac1{2m}\quad(2\le i\le m),\qquad
 r=\frac{2m+1}{4m}.
\end{equation}
The part $R$ provides a reservoir of possible matching partners for
the other parts, which we call satellites. Labels are constant on
each pair of parts and are given by
\begin{equation}\label{eq:general-lower-labels}
 \lambda(A_i,A_j)=\max\{1,\min(i,j)-1\},\qquad
 \lambda(A_i,R)=i,\qquad \lambda(R,R)=m+1.
\end{equation}
The first rule includes $i=j$ and hence specifies all internal
labels. When $\ell=4$, the proportions are $(1,2,2,7)/12$, and the
label matrix is exactly the one in~\cite{CP}.

\begin{proof}[Proof of Theorem~\ref{thm:general-lower}]
We prove an exact finite statement. For any positive integer $q$, take
$N=4mq$ vertices and parts of sizes
\[
 |A_1|=q,\qquad |A_i|=2q\ (2\le i\le m),\qquad
 |R|=(2m+1)q.
\]
Write $A=\bigcup_{i=1}^m A_i$, $s=|A|=(2m-1)q$, and
$r_N=|R|$. We claim that the minimum number of critical edges over
all perfect matchings is
\begin{equation}\label{eq:general-lower-finite}
 (4m^2-2m)q^2-(m-1)q.
\end{equation}

Fix a perfect matching. Let $x_i$ count its edges between $A_i$ and
$R$, and put
\[
 X=\sum_{i=2}^m x_i,\qquad
 p_i=\sum_{j<i}|A_j|.
\]
Thus $p_1=0$ and $p_i=(2i-3)q$ for $i\ge2$.
Every vertex in $A_i$ has birth at most $i$, because every edge
incident to $A_i$ has label at most $i$. An edge between $A_i$ and
$R$, whose label is $i$, is therefore critical if and only if its
endpoint in $R$ has birth greater than $i$. Exactly
$r_N-\sum_{j\le i}x_j$ vertices of $R$ have this property.
Consequently the number of critical edges between $A$ and $R$ is
\begin{equation}\label{eq:general-lower-cross-count}
 \sum_i |A_i|\left(r_N-\sum_{j\le i}x_j\right)
 =sr_N-\sum_i x_i(s-p_i).
\end{equation}

Let $U$ consist of those vertices in $A_i$, $i\ge2$, that are
matched to $R$. Every edge within $A$ incident to $U$ is critical:
the vertex in $A_i\cap U$ has birth $i$, whereas its edge to any
satellite has label smaller than $i$. Since $|U|=X$, these edges
number
\[
 \binom{s}{2}-\binom{s-X}{2}
 =sX-\frac{X^2+X}{2}.
\]
Adding this to \eqref{eq:general-lower-cross-count} yields
\begin{equation}\label{eq:general-lower-count-bound}
 C_\lambda(\M)\ge
 s(r_N-x_1)+\sum_{i=2}^m p_ix_i-\frac{X^2+X}{2}.
\end{equation}
All $0\le x_i\le2q$ for $i\ge2$. The identity
\[
 2\sum_{i=2}^m p_ix_i-X^2
 =\sum_{i=2}^m x_i(2q-x_i)
  +2\sum_{2\le i<j\le m}x_j(2q-x_i)
 \ge0
\]
therefore applies. Moreover $x_1\le q$ and $X\le2(m-1)q$.
Equation~\eqref{eq:general-lower-count-bound} now gives
\[
 C_\lambda(\M)\ge s(r_N-q)-(m-1)q
 =(4m^2-2m)q^2-(m-1)q.
\]
Empty sums are interpreted as zero, so the argument includes $m=1$.

Equality is attained by matching every vertex of $A$ to a distinct
vertex of $R$, and matching the remaining $2q$ vertices of $R$
internally. Indeed $x_1=q$, $x_i=2q$ for $i\ge2$, and the only
critical edges within $A$ are precisely those incident to $U$.
No edge inside $R$ is critical. This proves
\eqref{eq:general-lower-finite}. Dividing by $\binom{4mq}{2}$ and
letting $q\to\infty$ gives
\[
 \lim_{q\to\infty}
 \frac{(4m^2-2m)q^2-(m-1)q}{\binom{4mq}{2}}
 =\frac{2m-1}{4m},
\]
which proves the theorem by the definition of $\gamma'(\ell)$.
\end{proof}

The theorem gives $1/4,3/8,5/12,7/16,9/20$ for
$\ell=2,3,4,5,6$, respectively. For four labels the six-part
construction of Theorem~\ref{thm:lower-exact} gives a stronger
bound. The present family supplies a simple bound for every $\ell$.

\begin{proposition}\label{prop:general-lower-weights}
Keep the labels in \eqref{eq:general-lower-labels}, and allow
arbitrary nonnegative satellite proportions $a_1,\ldots,a_m$ and
reservoir proportion $r=1-\sum_i a_i\ge1/2$. Among these choices,
the largest possible minimum asymptotic critical density is
$(2m-1)/(4m)$. It is attained only at the proportions
\eqref{eq:general-lower-masses}.
\end{proposition}

\begin{proof}
Put $S=\sum_i a_i\le1/2$. There is a matching sending every
satellite vertex into the reservoir, with the remaining reservoir
vertices matched internally. Counting ordered pairs, its critical
density is
\[
 G(a)=2S-2S^2-\left(2a_1^2+\sum_{i=2}^m a_i^2\right).
\]
For clarity, its satellite contribution is $S^2-a_1^2$ and its
satellite--reservoir contribution is
$2\sum_i a_i(r-\sum_{j\le i}a_j)$; their sum is the displayed
expression. The minimum critical density over all matchings cannot
exceed $G(a)$.

Weighted Cauchy--Schwarz gives
\[
 2a_1^2+\sum_{i=2}^m a_i^2\ge\frac{2S^2}{2m-1}.
\]
It follows that
\[
 G(a)\le2S-\frac{4m}{2m-1}S^2
 =\frac{2m-1}{4m}
  -\frac{4m}{2m-1}\left(S-\frac{2m-1}{4m}\right)^2.
\]
Equality requires $S=(2m-1)/(4m)$ and
$a_2=\cdots=a_m=2a_1$, giving exactly
\eqref{eq:general-lower-masses}. For $m=1$ the same conclusion
follows directly from $S=a_1$. The finite construction already
proved attains this value. Approximation by rational proportions
justifies the count for arbitrary real masses.
\end{proof}

This optimality statement concerns the specified labels and the
condition $r\ge1/2$. It makes no assertion about other labelings or
about the same labeling with a reservoir of mass less than $1/2$.