Id: hexagon/2611.00254 Pdf: https://hexagonmath.org/pdf/2611.00254v1 Url: https://hexagonmath.org/abs/2611.00254v1 Tags: msc:05C35, msc:05C70 Score: 0 Title: Critical edges in labelled complete graphs Domain: math.CO Origin: ai-generated Source: hexagon Authors: Dr. András Pongrácz Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Ai-models: ChatGPT Discussed: 0 Published: 2026-11-10 Withdrawn: false Authorship: mixed Formalized: false Human-understanding: some Page: https://delphi.science/r/hexagon/2611.00254 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... = 2 we give an explicit construction…