Minimum blockers and extremal graphs for nonnested matchings
We classify all smallest sets of edge deletions that destroy every nonnested perfect matching in a complete ordered graph. The vertices have a fixed linear order. A perfect matching selects edges that use each vertex exactly once; it is nonnested when no selected edge has both endpoints strictly between those of another. On $2k$ vertices, exactly $k$ deletions are necessary, and we describe all $2^k+k-2$ minimum deletion sets for every $k\ge2$. Allowing a matching to leave vertices unused changes the extremal problem. Barát, Freschi and Tóth proposed that an $n$-vertex ordered graph avoiding…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.14484
curl -X POST /api/v1/records/arxiv/2609.14484/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.14484/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'