Ordered Ruzsa-Szemeredi Numbers at Matching Size Two

Abstract

Bondy and Szwarcfiter defined ${\mathrm{ex}}^{\ast }(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 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)-{\mathrm{ex}}^{\ast }(n,2K_2)$ is $\Theta (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 ${\mathrm{ORS}}_n(r)$ for the largest number of parts, so that $r{\mathrm{ORS}}_n(r)$ is the ordered analogue of ${\mathrm{ex}}^{\ast }(n,r{K}_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 ${\mathrm{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 ${\mathrm{ORS}}_{20}(2)$ to $\{78,79\}$. The counting bound $\lfloor n(n-4)/4\rfloor$ 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 $\frac{3}{2}n+O(1)$, and along powers of two a dyadic construction keeps it below $O(n\log 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.

26 pages, 2 figures. v2: substantially revised and extended. Ordered/unordered deficiency comparison added; exact values determined through order nineteen with order twenty confined to two values; Lean 4 formalisation of the structural results included, with a verified build; supplementary code and certificates included