arXiv, preprint, v2 · 8 October 2026 · 30 pages, 11 figures, 1 algorithm
Research account
Minimum blockers and extremal graphs for nonnested matchings
Place 2k vertices in a fixed order and join them in pairs, with no edge nested inside another. Which edge sets meet every such perfect matching? This asks how a global order constraint can be obstructed by a small set of deletions.
For k ≥ 2, we classify all minimum blockers into three explicit families. Each has k edges, and there are exactly 2k + k − 2 of them. The proof uses interval cuts and minimum spanning trees. It also yields a quadratic-time certifying algorithm: given at most k deleted edges, it returns a nonnested perfect matching or a minimum blocker contained in the deleted set.
The classification connects with blockers of 123-avoiding permutation matrices. Beyond the perfect-matching case, the expanded version constructs counterexamples to the proposed (k − 1)n extremal bound for every k ≥ 5 and n ≥ 2k + 1. For n ≥ 3k, the excess is proportional to k2, matching the order of the known upper bound on this excess. The exact extremal value remains open in general.
Version 2, dated 8 October 2026, substantially expands the constructions, proofs and illustrations: 30 pages, 11 figures and 1 algorithm.
The preprint is available on arXiv.