A note on Ordered Ruzsa-Szemerédi graphs
Kevin Pratt · 2025
Read A note on Ordered Ruzsa-Szemerédi graphs by Kevin Pratt (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02455.txt.
Description
Kevin Pratt settles a question left open by recent matching algorithms: two flavors of Ruzsa-Szemerédi graph are nearly the same. The note appeared in twenty twenty-five. These graphs, whose edges split into tidy induced matchings, now govern the speed of dynamic matching software.
The ordered variant relaxes the classic rule: each matching must be induced only within the matchings from its position onward. Pratt proves that if dense ordered examples exist, classic ones nearly as dense follow. Any polynomial density in the loose version transfers, losing only an arbitrarily small shaving of the exponent. The result ties the new algorithmic engine firmly to decades of combinatorics. It closes the gap the algorithm designers had flagged.
Catalog record
| CREATOR | Kevin Pratt |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 8 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-02455