\section{Introduction}\label{sec:introduction}
A matching in an edge-labelled complete graph assigns a label to each
vertex it covers: the label of its matching edge. We ask how to choose
a matching so that few graph edges have a smaller label than at least one of
the matching edges incident to them, that is, smaller than at least one of its endpoints. 
This extremal problem was introduced by Cs\'oka and Pongr\'acz~\cite{CP} in their study of
algorithms that find cliques and dense subgraphs by querying edges
of a random graph. We improve both upper bounds for arbitrary
labelings and lower bounds obtained from explicit constructions.

\subsection{The extremal parameters}
Let $K_N$ be a complete graph on $N$ vertices. 
Let $\lambda:E(K_N)\to\{1,\ldots,\ell\}$ be an edge labeling and
let $\M$ be a matching of size $M$. For a covered vertex $v$, define
$b_\M(v)$ to be the label of the unique matching edge incident to
$v$, and put $b_\M(v)=0$ for an uncovered vertex. We call this
number the \emph{birth label} of $v$. An edge $uv$ is \emph{critical}
for $\M$ when
\[
 \lambda(uv)<\max\{b_\M(u),b_\M(v)\}.
\]
For example, if $u$ is matched by an edge of label $3$, then every
edge of label $1$ or $2$ incident to $u$ is critical. A matching edge
itself is never critical. An edge from a covered vertex to an
uncovered vertex can be critical; such an edge is called
\emph{outward critical}.

Write $C_\lambda(\M)$ for the total number of critical edges,
including outward critical edges. Following~\cite{CP}, define
\begin{equation}\label{eq:gamma-definition}
 \gamma(\ell)=\limsup_{M\to\infty}\sup_{N\ge2M}\max_{\lambda}
       \min_{|\M|=M}\frac{C_\lambda(\M)}{\binom{2M}{2}}.
\end{equation}
Thus the labeling is chosen first and the matching second. The
normalizing denominator counts pairs among the $2M$ covered
vertices, even though the numerator also counts outward critical
edges. The perfect-matching version is
\[
 \gamma'(\ell)=\limsup_{M\to\infty}\max_{\lambda:E(K_{2M})\to[\ell]}
       \min_{\M\text{ perfect}}\frac{C_\lambda(\M)}{\binom{2M}{2}},
 \qquad [\ell]=\{1,\ldots,\ell\}.
\]
In particular $\gamma'(\ell)\le\gamma(\ell)$. An upper bound for
$\gamma(\ell)$ must work for arbitrarily many uncovered vertices;
a lower construction on $2M$ vertices already bounds both parameters
from below.

Cs\'oka and Pongr\'acz~\cite{CP} proved
$\gamma'(2)=\gamma(2)=1/4$ and $\gamma'(3)=\gamma(3)=3/8$.
For four labels their estimates were
\[
 \frac5{12}\le\gamma'(4)\le\gamma(4)\le\frac7{16}.
\]
For every $\ell\ge4$ they established
\begin{equation}\label{eq:CP-general-bound}
 \gamma(\ell)\le\frac12-\frac1{3\cdot2^{\ell-1}-4\ell+8}.
\end{equation}
They also showed that the corresponding parameter with arbitrarily
many labels equals $1/2$.

\subsection{Results}
\begin{theorem}\label{thm:main-bounds}
Let $\alpha_L$ be the algebraic number specified in
Section~\ref{sec:lower-exact}. Then
\[
 0.41977282048624007772\ldots=\alpha_L
 \le\gamma'(4)\le\gamma(4)\le\Gfrac=\Gnew.
\]
The lower bound is realized by a labeling on six vertex parts whose
proportions belong to a number field of degree six.
\end{theorem}

The lower bound extends the search for explicit extremal labelings,
whereas the upper bound asserts that every four-label instance has
an appropriate matching. The two estimates leave a gap; no equality
between $\gamma'(4)$ and $\gamma(4)$ is assumed.

\begin{theorem}\label{thm:main-general}
For every integer $\ell\ge2$,
\[
 \gamma'(\ell)\ge\frac12-\frac1{4(\ell-1)}.
\]
For $\ell\ge5$, put $k=2^{\ell-2}$ and $S=3k-2\ell+4$. Then
\[
 \gamma(\ell)\le\frac12-\frac1{2S}-\frac1{648k}.
\]
In addition,
\[
 \gamma(\ell)\le\frac12-\frac1{5k}
 +\frac{2\sqrt2}{25k^{3/2}}
 +O\!\left(\frac{\log k}{k^2}\right)
 \qquad(\ell\to\infty).
\]
\end{theorem}

The general lower construction has $\ell$ vertex parts. Its exact
finite matching minimum and the optimality of its part proportions
are proved in Section~\ref{sec:general-lower}. The optimality is
within the specified labeling family, with one part of mass at least
$1/2$. For $\ell=4$ it recovers $5/12$; the six-part construction
of Theorem~\ref{thm:main-bounds} gives the stronger value above.

The finite general upper bound improves
\eqref{eq:CP-general-bound} by $1/(162\cdot2^\ell)$. The asymptotic
upper bound increases the leading gap below $1/2$ from $1/(6k)$
to $1/(5k)$, a factor of $6/5$. The error term in that statement is
necessary. For finite $\ell$, Theorem~\ref{thm:general-full-budget}
gives a rational two-variable quadratic formula; it is this finite
formula, and the bound in Section~\ref{sec:general-shortened}, that
produce the following certified estimates.

\begin{center}
\begin{tabular}{ccc}
\toprule
$\ell$ & Lower bound & Upper bound\\\midrule
4 & $0.419772820486$ & $0.4334035$\\
5 & $7/16$ & $0.471876610486$\\
6 & $9/20$ & $0.487382111461$\\
7 & $11/24$ & $0.494116218018$\\
8 & $13/28$ & $0.497175259512$\\
9 & $15/32$ & $0.498622167790$\\
10 & $17/36$ & $0.499299501525$\\
11 & $19/40$ & $0.499630626700$\\
12 & $21/44$ & $0.499810572146$\\
\bottomrule
\end{tabular}
\end{center}
The lower bounds apply to $\gamma'$ and hence to $\gamma$. The
upper bounds apply to $\gamma$ and hence to $\gamma'$. Displayed
decimal lower bounds are rounded downward, and upper bounds upward.
The general-label upper entries are verified rational choices of
the parameters in the finite formulas; they are not claims of
optimality over all possible matching arguments.

\subsection{Proof strategy and organization}
The general lower construction in Section~\ref{sec:general-lower}
provides an elementary example of the problem. Its proof counts
critical edges for an arbitrary perfect matching, without a
computer calculation.

For the upper bounds, we start with a matching chosen by the order of~\cite{CP}. 
This order prevents several small exchanges that would reduce its weight. 
Those restrictions bound the number of critical edges inside and between the sets of vertices
covered by matching edges of each label. 
The original estimate is sharp only if several of these counts are simultaneously large.
We show that such a configuration permits other matchings with smaller critical-edge counts.

The four-label argument begins in Section~\ref{sec:foundations}.
We describe the exchanges explicitly and keep track of the edges
that prevent each exchange. This leads to a finite family of
quadratic inequalities. Section~\ref{sec:certificates} combines
these inequalities to prove the numerical bound. Each combination
has rational coefficients, and its validity is checked by an exact
matrix factorization. The combinatorial derivations are given in
the text; the supplied programs check the resulting identities,
signs, and coverage of the parameter ranges.

For general $\ell$, alternating paths provide a systematic family
of exchanges. Sections~\ref{sec:general-path-packing}--\ref{sec:general-path-full-budget}
derive the corresponding finite and asymptotic upper bounds.
The estimates account for outward critical edges, so the number of
uncovered vertices does not enter the error terms.

Section~\ref{sec:lower-exact} proves the six-part lower bound.
For a labeling constant on pairs of vertex parts, a matching is
described by the amount it matches between each pair of parts. These
amounts satisfy linear constraints, and the noncritical-edge count
is a quadratic function of them. We bound this function over the
entire feasible set using exact algebraic arithmetic. The algebraic
number and the part proportions are specified explicitly. Appendix~\ref{sec:lower-local-stability} examine
small perturbations of this construction. Section~\ref{sec:reproducibility}
gives the verification commands and identifies the data needed for
each computational claim.

Two normalizations occur in the proofs. Upper-bound counts are
divided by $M^2$, so their conversion to $\gamma$ includes a factor
of $1/2$, since $\binom{2M}{2}=2M^2-M$. Lower constructions use
vertex masses summing to one and the density of ordered critical
pairs; this is already on the $\gamma'$ scale. The convention is
stated again at the start of each argument.

\subsection{Application to clique queries}
Consider an Erd\H{o}s--R\'enyi graph $G(n,1/2)$ whose edges are
initially unknown. An algorithm may query at most $n^\delta$ pairs
in $\ell$ rounds, choosing all queries of a round before receiving
the answers to that round. Let $\alpha_*(\delta,\ell)$ be the
supremum of the constants $\alpha$ for which such an algorithm
finds a clique of size $(\alpha+o(1))\log_2 n$ with probability
tending to one. Computational time is unrestricted.

Feige, Gamarnik, Neeman, R\'acz, and Tetali~\cite{FGNRT} obtained
upper bounds in this query model, and Feige and Ferster~\cite{FF}
sharpened the analysis for two and three rounds. The clique-query
theorem of Cs\'oka and Pongr\'acz~\cite{CP} gives, for
$1\le\delta\le2$ and $\ell\ge3$,
\[
 \alpha_*(\delta,\ell)
 \le1+\sqrt{1-\frac{(2-\delta)^2}{4\gamma(\ell)}}.
\]
Consequently any upper bound $G_\ell$ for $\gamma(\ell)$ proved
here can replace $\gamma(\ell)$ on the right. In particular one
may use $G_4=\Gnew$. Our lower constructions bound the
combinatorial parameters; they do not assert the existence of
clique-query algorithms attaining the corresponding expression.