Minimum blockers and extremal graphs for nonnested matchings
Abstract
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 2k+k−2 minimum deletion sets for every k≥2. 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 a nonnested k-edge matching can have at most (k−1)n edges. We construct counterexamples for every k≥5 and n≥2k+1. For n≥3k, our constructions exceed the proposed value by a number of edges proportional to k2, matching the order of the known upper bound on this excess. The classification follows from cuts between consecutive intervals; the larger constructions coordinate deletions at the two ends of the vertex order. The exact extremal value remains open in general.
Related
- Perfect matchings in planar 3-connected graphs: girth five and minimum degree five
- Extremal Families for Matchings in Permutations
- Exact local spectral thresholds for perfect matchings in $3$-graphs and $3$-partite $3$-graphs
- Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
- The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
BibTeX
@misc{castro2026minimum,
title = {{Minimum blockers and extremal graphs for nonnested matchings}},
author = {Pedro M. M. de Castro},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.14484},
eprint = {2609.14484},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14484},
}
RIS
TY - UNPB
TI - Minimum blockers and extremal graphs for nonnested matchings
AU - Pedro M. M. de Castro
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2609.14484
UR - https://arxiv.org/abs/2609.14484
AB - 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≥2. 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 a nonnested k-edge matching can have at most (k−1)n edges. We construct counterexamples for every k≥5 and n≥2k+1. For n≥3k, our constructions exceed the proposed value by a number of edges proportional to k^2, matching the order of the known upper bound on this excess. The classification follows from cuts between consecutive intervals; the larger constructions coordinate deletions at the two ends of the vertex order. The exact extremal value remains open in general.
ER -