Ordered Ruzsa-Szemeredi Numbers at Matching Size Two
Abstract
Bondy and Szwarcfiter defined ex*(n,F) as the largest number of edges in an n-vertex graph whose edge set partitions into induced copies of F; for F=2K2 the deficiency binomn2−ex*(n,2K2) is Θ(n3/2). We study the ordered relaxation at fixed matching size, in which each part need only be induced in the union of itself with the parts that follow it; write ORSn(r) for the largest number of parts, so that r ORSn(r) is the ordered analogue of ex*(n,rK2). Our main tool is a characterisation valid for every r: an ordered decomposition into induced r-matchings is a sequence of steps that start from Kn and repeatedly delete a perfect matching from 2r vertices currently spanning a clique. Reading a decomposition backwards turns a condition about the ordering into a reachability question that an exhaustive search can settle. For r=2 we determine ORSn(2) exactly at orders five through nineteen, where it takes the values $1,3,5,8,11,14,19,23,28,34,40,47,54,62,70$, and we confine ORS20(2) to {78,79}. The counting bound ⌊ n(n−4)/4⌋ is attained at orders five through nine and at eleven, and missed by exactly one part at every other order below twenty, so order eleven is an isolated exception, not a parity effect. Across this range the ordered deficiency equals 3/2n+O(1), and along powers of two a dyadic construction keeps it below O(nlog n); whether it is linear for all n is our main open question. The structural results are formalised in Lean 4, and the searches are certified by fail-closed sweeps and an independent checker.
Related
- Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
- Ordered Trees with Linear Off-Diagonal Ramsey Numbers
- A General Upper Bound on Multicolor Ordered Ramsey Numbers
- Multicolor Ramsey numbers of ordered matchings
- Ordered Ramsey numbers of 3-uniform hypergraphs with bounded weak degeneracy
BibTeX
@misc{song2026ordered,
title = {{Ordered Ruzsa-Szemeredi Numbers at Matching Size Two}},
author = {Xidan Song and Ruifeng Cao},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.14695},
eprint = {2608.14695},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.14695},
}
RIS
TY - UNPB
TI - Ordered Ruzsa-Szemeredi Numbers at Matching Size Two
AU - Xidan Song
AU - Ruifeng Cao
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.14695
UR - https://arxiv.org/abs/2608.14695
AB - Bondy and Szwarcfiter defined ex^*(n,F) as the largest number of edges in an n-vertex graph whose edge set partitions into induced copies of F; for F=2K_2 the deficiency binomn2−ex^*(n,2K_2) is Θ(n^3/2). We study the ordered relaxation at fixed matching size, in which each part need only be induced in the union of itself with the parts that follow it; write ORS_n(r) for the largest number of parts, so that r ORS_n(r) is the ordered analogue of ex^*(n,rK_2). Our main tool is a characterisation valid for every r: an ordered decomposition into induced r-matchings is a sequence of steps that start from K_n and repeatedly delete a perfect matching from 2r vertices currently spanning a clique. Reading a decomposition backwards turns a condition about the ordering into a reachability question that an exhaustive search can settle. For r=2 we determine ORS_n(2) exactly at orders five through nineteen, where it takes the values $1,3,5,8,11,14,19,23,28,34,40,47,54,62,70$, and we confine ORS_20(2) to {78,79}. The counting bound ⌊ n(n−4)/4⌋ is attained at orders five through nine and at eleven, and missed by exactly one part at every other order below twenty, so order eleven is an isolated exception, not a parity effect. Across this range the ordered deficiency equals 3/2n+O(1), and along powers of two a dyadic construction keeps it below O(nlog n); whether it is linear for all n is our main open question. The structural results are formalised in Lean 4, and the searches are certified by fail-closed sweeps and an independent checker.
ER -