A note on Ordered Ruzsa-Szemerédi graphs

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 - \varepsilon\))-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, \cdots,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\).