Exact Ordered Ruzsa-Szemeredi Numbers for Matchings of Size Two

Abstract

An ordered Ruzsa-Szemeredi graph is a graph whose edge set is partitioned into equal-size matchings, each induced in the suffix of the ordering that begins with it. Behnezhad and Ghafari introduced them to parametrize the update time of fully dynamic matching, but almost nothing is known about the numbers themselves. Writing f(n) for the largest number of parts when the matchings have size two, we determine f(n) exactly for every order from five to nineteen, narrow order twenty to two consecutive values, and give an explicit asymptotic construction. The engine is a bijection between ordered decompositions and K_4-peelings of the complete graph, each step deleting a perfect matching from four vertices that currently span a clique. This yields the counting bound floor(n(n-4)/4) at once and reduces equality to whether a cubic or near-cubic remainder is reachable. Structural lemmas cut the candidates to connected bridgeless graphs, and a contraction correspondence carries odd orders to the even census one larger, leaving a finite case analysis that we discharge by isomorphism-free reverse search. The bound is attained only at orders five through nine and eleven, and missed by exactly one at every other order we reach. Order eleven is thus an isolated exception rather than a parity phenomenon: the natural equality conjecture fails, and fails irregularly. Upper bounds are certified by fail-closed sweeps over complete cubic censuses, and every decomposition is re-checked against the definition by an independent verifier. Which of its two values order twenty takes remains open.