HEXAGONbeta

Counterexamples to the multicolor nonnested matching conjecture

Primarily AI-generated textHuman understanding: all partsmath.CO — Combinatorics

Contributed by Pedro Machado Manhães de Castro ↗

Version 1 / Oct 18, 2026 / CC BY 4.0

Abstract

We show that excluding nested pairs can increase the number of vertices needed to force a matching of one color, disproving a conjecture of Barát, Gyárfás and Tóth. A matching consists of edges with no shared endpoint. In a fixed vertex order, two edges are nested if both endpoints of one lie between those of the other. For rr colors and a target of kk edges, the classical theorem guarantees a matching of one color on (r−1)(k−1)+2k(r-1)(k-1)+2k vertices when every pair is joined by an edge. For every r,k≥3r,k\ge3, we construct a coloring at this very threshold in which every such matching contains a nested pair. Thus the nonnested threshold is larger by at least one vertex. Already with three colors, ten vertices force three disjoint edges of one color, while our coloring makes every such triple contain a nested pair. The self-contained proof combines endpoint counts with two edge recolorings that obstruct the pairings allowed by the vertex order.

Provenance statement

This work was developed with substantial use of OpenAI's ChatGPT and Codex and Anthropic's Claude for literature searches, mathematical exploration, the development and review of proofs, and manuscript preparation. The author directed the research and contributed to successive revisions of the exposition, with particular attention to making the explanations, examples, and figures clearer for mathematically trained readers outside the immediate specialty. The manuscript is primarily AI-generated. The author understands the mathematical construction and proof presented here and takes responsibility for the mathematical content.

Tools used

OpenAI
ChatGPT
OpenAI
Codex
Anthropic
Claude Fable
Anthropic
Claude Opus

References

  1. J. Barát, A. Freschi and G. Tóth, Matchings avoiding ordered patterns . Preprint, arXiv:2512.15461v2 (2025). https://arxiv.org/abs/2512.15461.arXiv
  2. J. Barát, A. Gyárfás and G. Tóth, Monochromatic spanning trees and matchings in ordered complete graphs . Journal of Graph Theory 105 (4) (2024), 523--541. https://doi.org/10.1002/jgt.23058.DOI
  3. P. M. M. de Castro, Minimum blockers and extremal graphs for nonnested matchings . Preprint, arXiv:2609.14484v2 (2026). https://arxiv.org/abs/2609.14484v2.arXiv
  4. E. J. Cockayne and P. J. Lorimer, The Ramsey number for stripes . Journal of the Australian Mathematical Society (Series A) 19 (2) (1975), 252--256. https://doi.org/10.1017/S1446788700029554.DOI

Version history

  1. v1Submitted by Pedro Machado Manhães de CastroInitial depositCurrentOct 18, 2026