\documentclass[11pt]{article}
\usepackage[a4paper,margin=25mm]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools,booktabs,microtype}
\usepackage{xurl}
\setlength{\emergencystretch}{1em}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\M}{\mathcal M}
\newcommand{\Gnew}{0.4334035}
\newcommand{\Gfrac}{\frac{866807}{2000000}}
\title{Critical edges in labelled complete graphs}
\author{Andr\'as Pongr\'acz\\[2pt]
\small University of Debrecen, Institute of Mathematics\\
\small ORCID: \href{https://orcid.org/0000-0002-2771-8974}{0000-0002-2771-8974}}
\date{9 November 2026}
\begin{document}
\maketitle
\begin{abstract}
In a complete graph whose edges have labels $1,\ldots,\ell$, an edge
is critical for a matching if its label is smaller than that of a
matching edge sharing an endpoint. The parameter $\gamma(\ell)$
is the asymptotic worst-case, over labelings, of the smallest critical-edge
count obtainable by choosing the matching, normalized by the number
of pairs of covered vertices; $\gamma'(\ell)$ is its perfect-matching version. These
parameters arise in bounds for finding cliques in random graphs by
edge queries in a prescribed number of rounds.
We prove
\[
0.419772820486\ldots\le\gamma'(4)\le\gamma(4)\le0.4334035.
\]
For every $\ell\ge2$ we give an explicit construction proving
$\gamma'(\ell)\ge1/2-1/[4(\ell-1)]$. 
We also improve the state-of-the-art upper bounds for general $\ell$, obtaining
\[
\gamma(\ell)\le\frac12-\frac{4}{5\cdot2^\ell}
+O(2^{-3\ell/2})\qquad(\ell\to\infty),
\]
together with explicit finite bounds. The proofs of upper bounds compare
matchings obtained by local exchanges. The proofs of lower bounds use
labelings that are constant on pairs of vertex parts; the stronger
four-label construction has six parts and an algebraic value of
degree six. Exact-arithmetic verification programs and their data
are included for the computer-assisted parts of the proofs.
\end{abstract}
\tableofcontents
\input{introduction}
\input{general-lower}
\input{foundations}
\input{proof}
\input{base-certificate}
\input{intersection}
\input{ap}
\input{auxiliary-ledgers}
\input{swapped}
\input{top-capacity}
\input{certificate}
\input{general-paths}
\input{general-layers}
\input{general-budget}
\input{lower}
\input{reproducibility}
\appendix
\input{lower-stability}
\input{lower-directional}
\section*{Acknowledgment}
The author was supported by the NRDI grant KKP~138270.

\input{references}
\end{document}