  In a very recent breakthrough, Behnezhad and Ghafari [arXiv'24] developed a
novel fully dynamic randomized algorithm for maintaining a
$(1-\epsilon)$-approximation of maximum matching with amortized update time
potentially much better than the trivial $O(n)$ update time. The runtime of the
BG algorithm is parameterized via the following graph theoretical concept:
  * For any $n$, define $ORS(n)$ -- standing for Ordered RS Graph -- to be the
largest number of edge-disjoint matchings $M_1,\ldots,M_t$ of size $\Theta(n)$
in an $n$-vertex graph such that for every $i \in [t]$, $M_i$ is an induced
matching in the subgraph $M_{i} \cup M_{i+1} \cup \ldots \cup M_t$.
  Then, for any fixed $\epsilon > 0$, the BG algorithm runs in \[
  O\left( \sqrt{n^{1+O(\epsilon)} \cdot ORS(n)} \right) \] amortized update
time with high probability, even against an adaptive adversary. $ORS(n)$ is a
close variant of a more well-known quantity regarding RS graphs (which require
every matching to be induced regardless of the ordering). It is currently only
known that $n^{o(1)} \leqslant ORS(n) \leqslant n^{1-o(1)}$, and closing this
gap appears to be a notoriously challenging problem.
  In this work, we further strengthen the result of Behnezhad and Ghafari and
push it to limit to obtain a randomized algorithm with amortized update time of
\[
  n^{o(1)} \cdot ORS(n) \] with high probability, even against an adaptive
adversary. In the limit, i.e., if current lower bounds for $ORS(n) = n^{o(1)}$
are almost optimal, our algorithm achieves an $n^{o(1)}$ update time for
$(1-\epsilon)$-approximation of maximum matching, almost fully resolving this
fundamental question. In its current stage also, this fully reduces the
algorithmic problem of designing dynamic matching algorithms to a purely
combinatorial problem of upper bounding $ORS(n)$ with no algorithmic
considerations.
