Monochromatic non-nested matching in 2-edge-colored Kₘ
Problem 1.1 · arXiv:2511.02892
Status partial high confidence
Problem 1.1 asks for the smallest $m$ guaranteeing a monochromatic non-nested matching of size $n$ in every 2-coloring of ordered $K_m$. The answer lies between $3n-1$ (the lower bound, conjectured by Barát to be exact) and $(2+\sqrt{3})n \approx 3.73n$ (a Turán-type upper bound established in arXiv:2512.15461 by Barát, Freschi, and Tóth). The conjecture that $3n-1$ is the precise threshold remains open.
Cited literature (1)
-
Establishes via a Turán-type extremal argument that every 2-coloring of ordered $K_m$ with $m > (2+\sqrt{3})n$ contains a monochromatic non-nested matching of size $n$, improving the prior upper bound of $4n-2$; the conjecture $m = 3n-1$ remains open.
Reviewer notes. Reference [2] of the source paper is Barát–Gyárfás–Tóth (J. Graph Theory 105(4):523–541, 2024; arXiv:2210.10135), which first conjectured that $3n-1$ is the exact answer. The source paper restates this as Problem 1.1 and already records the $(2+\sqrt{3})n$ upper bound (its Proposition 1.1) as obtained from unpublished work; arXiv:2512.15461 is the formal public write-up of that Turán-type argument, posted one month after the source paper.
Context
Two independent edges $ij$ and $st$ in an ordered complete graph are nested if $i<s<t<j$ or $s<i<j<t$. The answer is known to lie between $3n-1$ and $4n-2$; the presenting author conjectured (in prior work [2]) that the lower bound $3n-1$ is optimal. A Turán-type approach recently improved the upper bound to $(2+\sqrt{3})n$.
Source paper
Open problems of the 33rd Workshop on Cycles and Colourings
János Barát, Zdeněk Dvořák, Penny Haxell, František Kardoš, Borut Lužar, Alfréd Onderko, Jozef Rajník, Roman Soták, Nikolay Ulyanov · 2025-11-04
https://arxiv.org/abs/2511.02892