A note on Ordered Ruzsa-Szemerédi graphs

Abstract

A recent breakthrough of Behnezhad and Ghafari [FOCS 2024] and subsequent work of Assadi, Khanna, and Kiss [SODA 2025] gave algorithms for the fully dynamic $(1-\epsilon )$-approximate maximum matching problem whose runtimes are determined by a purely combinatorial quantity: the maximum density of Ordered Ruzsa-Szemerédi (ORS) graphs. We say a graph $G$ is an $(r,t)$-ORS graph if its edges can be partitioned into $t$ matchings $M_1,M_2,\dots ,M_t$ each of size $r$, such that for every $i$, $M_i$ is an induced matching in the subgraph $M_i\cup M_{i+1}\cup \cdots \cup M_t$. This is a relaxation of the extensively-studied notion of a Ruzsa-Szemerédi (RS) graph, the difference being that in an RS graph each $M_i$ must be an induced matching in $G$. In this note, we show that these two notions are roughly equivalent. Specifically, let $\mathrm{ORS}(n)$ be the largest $t$ such that there exists an $n$-vertex ORS-$(\hat{I}\text{c◯}(n),t)$ graph, and define $\mathrm{RS}(n)$ analogously. We show that if $\mathrm{ORS}(n)\ge \hat{I}\text{c◯}(n^c)$, then for any fixed $\hat{I}´>0$, $\mathrm{RS}(n)\ge \hat{I}\text{c◯}(n^{c(1-\hat{I}´)})$. This resolves a question of Behnezhad and Ghafari.