Overview
Research has focused on determining ordered Ruzsa-Szemeredi numbers for graphs where the edge set is partitioned into equal-sized matchings. Specifically, this study investigates $f(n)$, which represents the largest number of parts when these matchings are each of size two. While these numbers were introduced to parametrize the update time of fully dynamic matching by Behnezhad and Ghafari, almost nothing was known about their values prior to this work.
Research Context
The concept of an ordered Ruzsa-Szemeredi graph involves a graph with an edge set partitioned into matchings of equal size. These matchings are induced within the suffix of the ordering that commences with each respective matching. The variable $f(n)$ quantifies the maximum number of such parts under the specific condition that each matching has a size of two. The initial introduction of these graphs and numbers aimed to characterize the update time in fully dynamic matching processes.
Approach
The methodology employed for this determination hinges on a bijection established between ordered decompositions and K4-peelings of the complete graph. Each step of this peeling process involves deleting a perfect matching from four vertices that currently span a clique. This foundational bijection immediately yields a counting bound of $\text{floor}(n(n-4)/4)$.
The task of achieving equality with this bound was reduced to determining whether a cubic or near-cubic remainder is reachable. Structural lemmas were applied to narrow the candidate graphs to connected bridgeless configurations. A contraction correspondence was utilized to map odd orders to the even census one size larger, simplifying the problem. This left a finite case analysis, which was discharged through an isomorphism-free reverse search technique.
Upper bounds were certified through fail-closed sweeps conducted over complete cubic censuses. Furthermore, every decomposition identified was independently re-checked against its definition by an independent verifier to ensure accuracy.
Findings
The research determined $f(n)$ exactly for every order from five to nineteen. For order twenty, the value was narrowed down to two consecutive potential values. An explicit asymptotic construction was also provided.
The derived bound, $\text{floor}(n(n-4)/4)$, was observed to be attained precisely at orders five through nine, and additionally at order eleven. For all other orders reached within the study, the bound was missed by exactly one unit. This indicates that order eleven represents an isolated exception, rather than being part of a broader parity phenomenon. Consequently, a natural equality conjecture regarding these numbers was found to fail, and its failure exhibited an irregular pattern.
The specific value for order twenty remains an open question, with its exact determination requiring further investigation between the two identified consecutive values.