HEXAGONbeta

Critical edges in labelled complete graphs

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Dr. András Pongrácz ↗

Version 1 / Nov 10, 2026 / CC BY 4.0

Abstract

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.

Provenance statement

AI assistance was used in developing the mathematical arguments, verification programs, and exposition. The complete exact-arithmetic verification suite was run successfully on the accompanying files. The computations check finite algebraic certificates; the combinatorial arguments and the elementary general lower bound are presented in the paper.

Tools used

OpenAI
ChatGPTVersion GPT-6 Astra

References

  1. E. Csóka and A. Pongrácz, Finding cliques and dense subgraphs using edge queries , Discrete Mathematics 349 (10) (2026), 115226. doi:10.1016/j.disc.2026.115226 (https://doi.org/10.1016/j.disc.2026.115226). Preprint: arXiv:2310.06826 (https://arxiv.org/abs/2310.06826).arXivDOI
  2. U. Feige, D. Gamarnik, J. Neeman, M. Z. Rácz, and P. Tetali, Finding cliques using few probes , Random Structures & Algorithms 56 (1) (2020), 142--153. doi:10.1002/rsa.20896 (https://doi.org/10.1002/rsa.20896).DOI
  3. U. Feige and T. Ferster, A tight bound for the clique query problem in two rounds , arXiv:2112.06072 (2021). https://arxiv.org/abs/2112.06072.arXiv
  4. D. Kőnig, Graphok és matrixok , Matematikai és Fizikai Lapok 38 (1931), 116--119. English translation by G. Szárnyas, arXiv:2009.03780 (2020), https://arxiv.org/abs/2009.03780.arXiv
  5. P. Erdős and T. Gallai, On maximal paths and circuits of graphs , Acta Mathematica Academiae Scientiarum Hungaricae 10 (1959), 337--356. https://users.renyi.hu/~p_erdos/1959-10.pdf.link
  6. W. T. Tutte, The factorization of linear graphs , Journal of the London Mathematical Society 22 (2) (1947), 107--111. doi:10.1112/jlms/s1-22.2.107 (https://doi.org/10.1112/jlms/s1-22.2.107).DOI
  7. C. Berge, Two theorems in graph theory , Proceedings of the National Academy of Sciences of the USA 43 (9) (1957), 842--844. doi:10.1073/pnas.43.9.842 (https://doi.org/10.1073/pnas.43.9.842).DOI
  8. A. Schrijver, Tutte--Berge ⇒\Rightarrow Gallai ⇒\Rightarrow Mader , seminar notes, https://homepages.cwi.nl/~lex/files/mader_gallai_tutteb.pdf, accessed 9 November 2026.link
  9. L. Lovász, Large Networks and Graph Limits , American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. doi:10.1090/coll/060 (https://doi.org/10.1090/coll/060).DOI
  10. H. Peyrl and P. A. Parrilo, Computing sum of squares decompositions with rational coefficients , Theoretical Computer Science 409 (2) (2008), 269--281. doi:10.1016/j.tcs.2008.09.025 (https://doi.org/10.1016/j.tcs.2008.09.025).DOI

Version history

  1. v1 · 62 pagesSubmitted by Dr. András PongráczInitial depositCurrentNov 09, 2026