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.

Disclosure

“etween 78 and 79 remains open. Determining that choice, continuing exact computation from order 21, and explaining structurally why the counting bound fails remain open. Declaration on the use of generative AI. OpenAI ChatGPT/Codex and Anthropic Claude (accessed July–August 2026) assisted with source discovery, ex- ploratory proof development and checking, manuscript drafting and revision, soft- ware development and review, test design, and orchestration of computational checks. Their ou”

PDF page 13

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:06:37.512518Z

Structural counts