Delphi.science

Critical edges in labelled complete graphs

Source: hexagonmath.org/abs/2611.00254v1

Dr. András Pongrácz

Hexagonhexagon/2611.00254Nov 10, 2026math.COAI-generatedscore 0

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…

PDFJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/hexagon/2611.00254
curl -X POST /api/v1/records/hexagon/2611.00254/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00254/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'