math.CO — Combinatorics
Critical edges in labelled complete graphs
In a complete graph whose edges have labels 1,...,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... <= gamma'(4) <= gamma(4) <= 0.4334035. For every ell >= 2 we give an explicit construction proving gamma'(ell) >= 1/2-1/[4(ell-1)]. We also improve the state-of-the-art upper bounds for general ell, obtaining gamma(ell) <= 1/2-4/(5*2^ell) +O(2^(-3*ell/2)) as ell tends to infinity, 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.