REVIEW 4 minor 2 cited by
A note on Ordered Ruzsa-Szemer\'edi graphs
T0 review · 0 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read This paper proves that ordered Ruzsa-Szemerédi graphs are roughly as dense as ordinary Ruzsa-Szemerédi graphs, closing a gap that would have made the ordered notion strictly more powerful.
desk verdict A short, clean proof that ORS and RS graphs have polynomially equivalent max density; the main argument is sound and the paper deserves refereeing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The construction $H_s$ is the central object. Given an ORS graph $G = M_1 \cup \cdots \cup M_t$ on $n$ vertices, $H_s$ has vertex set $V(G)^k$, and an edge is a pair of $k$-tuples $(U,V)$ such that each coordinate $(U_i,V_i)$ is an edge of $G$ and the matching indices $f(U_i,V_i)$ sum to $s$. The edges partition into matchings $M_a$ indexed by $k$-tuples $a$ with $\sum a_i = s$, and each $M_a$ is shown to be an induced matching by the coordinate-wise inequality $f(U_i,V_i) \le a_i$ that follows from the ORS suffix condition. Pigeonhole averaging over $s$ yields many matchings.
What would settle it
A concrete counterexample would be a family of $n$-vertex ORS graphs with $\mathrm{ORS}(n, \varepsilon n) \ge n^c$ for some fixed $c>0$ while $\mathrm{RS}(n, \Theta(\varepsilon^{1/\delta} n)) \le n^{c(1-\delta)-\omega(1)}$ for some fixed $\delta>0$; exhibiting such graphs would disprove the theorem's tightness. Alternatively, a direct computation of ORS and RS for the known constructions at growing $n$ that shows a superpolynomial gap would falsify the rough equivalence.
Extended reading notes
Core claim
The central claim is Theorem 1.3: if $\mathrm{ORS}(n, \varepsilon n) \ge \Omega(n^c)$, then for every fixed $\delta > 0$, $\mathrm{RS}(n, \Theta(\varepsilon^{1/\delta} n)) \ge \Omega(n^{c(1-\delta)})$. This is proved by a tensor-power construction: from an $n$-vertex ORS graph with $t$ matchings of size $r$, one builds an $n^k$-vertex graph whose edges are $k$-tuples of ORS edges whose matching indices sum to a fixed value $s$. That graph is partitioned into $t^{k-1}/k$ matchings of size $r^k$, each of which is an induced matching in the full graph. The proof exploits the ORS 'suffix-induced' property to bound each coordinate of an edge in the induced subgraph, then uses equality of the coordinate sums to force exact membership. As a consequence, the maximum density of ORS graphs with linear matchings is roughly equivalent to the same quantity for ordinary RS graphs.
Load-bearing premise
The proof needs the ORS definition's suffix condition: each matching $M_i$ must be induced in the union of the matchings from $i$ onward, not merely in the whole graph; if the definition were weakened to whole-graph inducedness, the coordinate-wise bound $f(U_i,V_i) \le a_i$ would not hold and the construction would collapse.
Editorial extensions
If this is right
- If $\mathrm{ORS}(n, \varepsilon n) \ge \Omega(n^c)$, then $\mathrm{RS}(n, \Theta(\varepsilon^{1/\delta} n)) \ge \Omega(n^{c(1-\delta)})$ for any fixed $\delta > 0$.
- The fully dynamic matching algorithm of Assadi, Khanna, and Kiss can be restated with update time $n^{o(1)} \cdot \mathrm{RS}(n, \Theta_\varepsilon(n))$, tying dynamic matching performance directly to the classic RS quantity.
- It is impossible that $\mathrm{RS}(n) = n^{o(1)}$ while $\mathrm{ORS}(n) = n^{1-o(1)}$; the two notions must have the same asymptotic behavior up to arbitrarily small polynomial factors.
- If the dynamic matching algorithm's update time turns out to be polynomial, then current constructions of both ORS and RS graphs are far from optimal.
Reading between the lines
- The tensor-power loss of $\delta$ in the exponent is likely inherent to the proof technique, but the same construction may transfer other 'suffix-induced' graph properties to ordinary induced matchings, potentially useful for other dynamic data structure problems.
- One could conjecture a sharper equivalence, namely $\mathrm{ORS}(n, \varepsilon n) = \mathrm{RS}(n, \Theta(\varepsilon n))^{1-o(1)}$, meaning the two quantities are subpolynomially equivalent even without fixing a polynomial regime.
- A practical testable extension would be to compute the best known ORS and RS constructions side by side for moderate $n$ to see whether the ratio grows slowly or remains near 1, which would hint at whether the polynomial loss is an artifact of the proof.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This note proves that Ordered Ruzsa-Szemerédi (ORS) graphs and classical Ruzsa-Szemerédi (RS) graphs have polynomially equivalent extremal densities for linear-sized matchings. Concretely, if ORS(n, εn) ≥ Ω(n^c), then for every fixed δ > 0, RS(n, Θ(ε^{1/δ} n)) ≥ Ω(n^{c(1−δ)}). The proof tensorizes a given ORS graph: for each k-tuple of matching indices, it forms a matching in the k-th tensor power, verifies via the suffix-induced ORS property that these matchings are induced, and applies a pigeonhole argument over the sum of indices. The author notes that this answers a question of Behnezhad and Ghafari and implies that the dynamic matching algorithm of Assadi–Khanna–Kiss can be stated in terms of ordinary RS graphs.
Significance. If correct, the result is a clean and useful equivalence: it rules out the possibility that ORS graphs are much denser than RS graphs, and it transfers the combinatorial bottleneck in recent fully dynamic matching algorithms to the classical RS quantity. The proof is self-contained, elementary, and short; the tensor construction and the coordinate-wise use of the ORS property are elegant. The note is fully rigorous apart from a harmless counting slip (see minor comments), and it resolves an explicitly posed question. The contribution is modest but appropriate for a note.
minor comments (4)
- [Section 2, Lemma 2.1] The equality |M_a| = r^k is not correct for an undirected graph: each k-tuple of undirected edges from M_{a_1},...,M_{a_k} gives rise to 2^{k-1} unordered edges of H_s, so |M_a| = 2^{k-1} r^k. This does not invalidate the lemma because the matchings are larger than claimed; delete edges from each M_a to leave exactly r^k edges, which preserves the induced-matching property, and then the stated bound follows. Please correct the counting and include the deletion step.
- [Section 2, definition of H_s] The edge set E(H_s) is written with ordered pairs, which is inconsistent with the subsequent treatment of H_s as an undirected graph; define E(H_s) as the set of unordered pairs {U,V} satisfying the stated condition.
- [Abstract and Theorem 1.3] The abstract's quantities ORS(n) and RS(n) hide the constant ε in 'Ω(n)' matchings. Since the proof requires a fixed ε with ORS(n, εn) ≥ Ω(n^c), the abstract should either refer to the parameterized statement or explicitly state that the constant ε is fixed across n.
- [Section 2, Lemma 2.1 proof] The phrase 'if any vertex U ∈ M_a' should be 'if any vertex U incident to an edge of M_a' for precision.
Circularity Check
No circular reasoning: the ORS-to-RS tensor construction is derived from the definitions and does not assume its conclusion.
full rationale
The paper's derivation chain is self-contained. Theorem 1.3's only inputs are the definition of an ORS graph and the hypothesis ORS(n, εn) ≥ Ω(n^c). Lemma 2.1 constructs H_s as the coordinate-wise k-th power of an ORS graph, partitions its edges by the matching-index vector a, and proves each M_a is an induced matching using exactly the ORS property that no M_j edge with j > i appears in the subgraph induced by the endpoints of M_i. The equality of sums then forces f(U_i,V_i) = a_i for every coordinate, so the claimed edge lies in M_a. The number of matchings is bounded by a pigeonhole argument over the possible sums s; no RS lower bound is assumed anywhere. Citations to [BCC+17] and [CFTZ22] are only motivational for the tensor-power trick and are not load-bearing. There are no fitted parameters, no self-citation chain, and no renaming of known results. The only technical blemish is that |M_a| is counted as r^k whereas, for undirected graphs, unordered edges are double-counted; this constant factor only makes each M_a larger, and since any subset of an induced matching is still an induced matching, the stated bound RS(n^k, r^k) ≥ t^{k-1}/k and the asymptotic theorem remain valid. This is a correctness nit, not circularity.
Assumptions & free parameters
assumptions (2)
- standard math Pigeonhole principle for distributing t^k solutions among at most kt sums.
- domain assumption Deleting vertices or edges from an RS graph preserves the RS property.
Cite this review
Pith. "Pith review of A note on Ordered Ruzsa-Szemer\'edi graphs." pith.science (2026). https://pith.science/paper/GIIBKFPC
@misc{pith2026250202455,
author = {Pith},
title = {Pith review of: A note on Ordered Ruzsa-Szemer\'edi graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/GIIBKFPC}},
note = {Machine review of arXiv:2502.02455}
}
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-\varepsilon)$-approximate maximum matching problem whose runtimes are determined by a purely combinatorial quantity: the maximum density of Ordered Ruzsa-Szemer\'edi (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, \ldots, 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\'edi (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-$(\Omega(n), t)$ graph, and define $\mathrm{RS}(n)$ analogously. We show that if $\mathrm{ORS}(n) \ge \Omega(n^c)$, then for any fixed $\delta > 0$, $\mathrm{RS}(n) \ge \Omega(n^{c(1-\delta)})$. This resolves a question of Behnezhad and Ghafari.
Forward citations
Cited by 2 Pith papers
-
Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints
A new blueprint framework proves single-pass semi-streaming matching cannot beat (8−2√10)/3 ≈ 0.558 approximation.
-
An improved construction for the triangle removal lemma
A new construction lowers the triangle-removal-lemma lower-bound exponent constant from about 0.83 to about 1.66, using a Euclidean-ball sumset estimate.
Reference graph
Works this paper leans on
-
[1]
Sepehr Assadi, Sanjeev Khanna, and Peter Kiss, Improved bounds for fully dynamic matching via ordered ruzsa-szemeredi graphs, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2025, pp. 2971--2990
work page 2025
-
[2]
Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A Grochow, Eric Naslund, William F Sawin, and Chris Umans, On cap sets and the group-theoretic approach to matrix multiplication, Discrete Analysis (2017)
work page 2017
- [3]
- [4]
-
[5]
Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam, Larger corner-free sets from combinatorial degenerations, ITCS 2022-13th Innovations in Theoretical Computer Science Conference, 2022, pp. 1--2410
work page 2022
- [6]
-
[7]
Jacob Fox, A new proof of the graph removal lemma, Annals of Mathematics (2011), 561--579
work page 2011
-
[8]
Yang P. Liu, On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication , 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) (Los Alamitos, CA, USA), IEEE Computer Society, October 2024, pp. 228--243
work page 2024
Show all 10 references
-
[9]
Imre Z Ruzsa and Endre Szemer \'e di, Triple systems with no six points carrying three triangles, Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18 (1978), no. 939-945, 2
1978
-
[10]
325--334
Shay Solomon, Fully dynamic maximal matching in constant update time, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 325--334
2016
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.