Fully Dynamic Matching and Ordered Ruzsa-Szemer\'edi Graphs

We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge insertions and deletions. Our focus is particularly on algorithms that maintain the edges of a (1-) -approximate maximum matching for an arbitrarily small constant > 0. Until recently, the fastest known algorithm for this problem required (n) time per update where n is the number of vertices. This bound was slightly improved to n/ (^* n) ^ (1) by Assadi, Behnezhad, Khanna, and Li STOC'23 and very recently to n/2^ (n) by Liu ArXiv'24. Whether this can be improved to n^1- (1) remains a major open problem. In this paper, we present a new algorithm that maintains a (1-) -approximate maximum matching. The update-time of our algorithm is parametrized based on the density of a certain class of graphs that we call Ordered Ruzsa-Szemer\'edi (ORS) graphs, a generalization of the well-known Ruzsa-Szemer\'edi graphs. While determining the density of ORS (or RS) remains a hard problem in combinatorics, we prove that if the existing constructions of ORS graphs are optimal, then our algorithm runs in n^1/2+O () time for any fixed > 0 which would be significantly faster than existing near-linear in n time algorithms. Our second main contribution is a better upper bound on density of both ORS and RS graphs with linear size matchings. The previous best upper bound was due to a proof of the triangle-removal lemma from more than a decade ago due to Fox Annals of Mathematics '11.