Fully Dynamic Matching and Ordered Ruzsa-Szemerédi 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1-\varepsilon)$</tex> -approximate maximum matching for an arbitrarily small constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon &gt; 0$</tex>. Until recently, the fastest known algorithm for this problem required <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Theta(n)$</tex> time per update where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> is the number of vertices. This bound was slightly improved to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n/(\log^{\ast}n)^{\Omega(1)}$</tex> by Assadi, Behnezhad, Khanna, and Li [STOC'23] and very recently to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n/2_{-}^{\Omega(\sqrt{\log n})}$</tex> by Liu [FOCS'24]. Whether this can be improved to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n^{1-\Omega(1)}$</tex> remains a major open problem. In this paper, we introduce Ordered Ruzsa-Szemerédi (ORS) graphs (a generalization of Ruzsa-Szemerédi graphs) and show that the complexity of dynamic matching is closely tied to them. For <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta &gt; 0$</tex>, define ORS <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\delta n)$</tex> to be the maximum number of matchings <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M_{1}, \ldots, 1M_{t}$</tex>, each of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta n$</tex>, that one can pack in an n-vertex graph such that each matching <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M_{i}$</tex> is an induced matching in subgraph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M_{1}\cup\ldots\cup M_{i}$</tex>. We show that there is a randomized algorithm that maintains a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1-\varepsilon)$</tex> -approximate maximum matching of a fully dynamic graph in amortized update-time. While the value of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{ORS}(\Theta(n))$</tex> remains unknown and is only upper bounded by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n^{1-o(1)}$</tex>, the densest construction known from more than two decades ago only achieves <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$ORS (\Theta(n))\geq n^{1/\Theta(\log\log n)}=n^{o(1)}$</tex> [Fischer et al. STOC'02]. If this is close to the right bound, then our algorithm achieves an update-time of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\sqrt{n^{1+O(\varepsilon)}}^{-}$</tex>, resolving the aforementioned longstanding open problem in dynamic algorithms in a strong sense.