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

CREATORKevin Pratt
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE8 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02455

Browse the full library · About the Tower of Babel