Critical edges in labelled complete graphs
Source: hexagonmath.org/abs/2611.00254v1
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…
Comments and reviews
No comments yet.
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}'