Using the Quadratic Lower Bound for Matching Estimation to Settle a Combinatorial Conjecture

Estimating the size of the largest matching in a graph, meaning the largest set of edges that share no endpoints, is a central test case for sublinear algorithms. These are algorithms that read only a small part of the input. A recent line of work has tied the cost of maintaining a near-optimal matching under edge insertions and deletions to a single unknown number: the maximum density of "ordered Ruzsa–Szemerédi" (ORS) graphs. These are graphs whose edges split into a sequence of matchings, each one induced with respect to the matchings that come before it. If ORS graphs are always sparse, near-optimal dynamic matching is nearly free. Nobody knows whether they are sparse. In the parallel world of static query algorithms, the question is settled without any conjecture: estimating matching size to within $\epsilon n$ additive error needs almost $n^2$ queries.

This proposal connects the two facts and uses the connection in the unusual direction. The plan is to build a static query algorithm for near-optimal matching estimation whose cost is bounded by ORS density. If that succeeds, the known unconditional quadratic lower bound becomes a proof that ORS graphs are polynomially dense. That would resolve the conjecture underlying the dynamic results, and it would resolve it against the hopeful case. The direction of the argument matters. Here a hardness result proves something about an unproven hypothesis, rather than the hypothesis being assumed in order to prove hardness.

Core Claim

The two inputs are a conditional upper bound and an unconditional lower bound.

The conditional upper bound comes from the dynamic setting. Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs introduced ORS graphs. It gave an update time of $\tilde{O}(\sqrt{n^{1+\epsilon}}\cdot \text{ORS}_\epsilon(n))$, built on a static subroutine that both approximates the matching and certifies the approximation. Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs removed the polynomial overhead and reached $n^{o(1)}\cdot\text{ORS}(n,\Theta_\epsilon(n))$. The research file states that this second paper explicitly does not transfer the reduction to static query algorithms. The only known bounds on ORS density are an unconditional upper bound of $\tilde O(n/\log^{(l)} n)$ and the trivial $n^{o(1)}$ floor.

The unconditional lower bound is Approximating Maximum Matching Requires Almost Quadratic Time. It shows that for every $\delta>0$ there is an $\epsilon>0$ such that additive-$\epsilon n$ estimation needs $\Omega(n^{2-\delta})$ adjacency-list queries, even on bipartite graphs.

The central target is an algorithm in the adjacency-list model, with pair queries, that estimates matching size to within $\epsilon n$. Here $c$ is a constant independent of $n$, and $\text{ORS}_\epsilon(n)$ is the largest number of matchings, each of size at least $\epsilon n$, in an ORS graph on $n$ vertices. The target query complexity is

$$ Q(n,\epsilon) \;\le\; n^{1+o(1)}\cdot \text{ORS}_{\epsilon'}(n)^{c}, \qquad \epsilon' = \text{poly}(\epsilon). $$

Put this next to the lower bound $Q \ge n^{2-\delta}$. Algebra then gives $\text{ORS}_{\epsilon'}(n) \ge n^{(1-\delta)/c - o(1)}$. This would be the first polynomial lower bound on ORS density. It would also show that the Assadi–Khanna route cannot give $n^{o(1)}$ dynamic update time.

The contrapositive is equally informative. If ORS graphs are in fact sparse, no such algorithm can exist. Finding exactly where the construction fails then shows which part of dynamic history the static model lacks. The analogous use of Ruzsa–Szemerédi density appears in A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching, which bounds the two-pass approximation ratio by $1-\Omega(\log RS(n)/\log n)$. That work motivates ours by showing that induced-matching density governs matching barriers. It differs in that it assumes the conjecture in order to derive hardness. We try to derive the conjecture from hardness.

Research Program

The algorithm has three stages, with one technical crux between the first two.

The first stage computes a starting matching locally. It uses the randomized greedy maximal matching oracle from Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. That oracle gives a 2-approximation at $\tilde O(n)$ cost and fixes a random ordering of edges, which serves as a "pseudo-history" in place of the update sequence a dynamic algorithm would have. This is the method-supplying use of that paper.

The second stage runs rounds of sampled search for short augmenting paths. An augmenting path is a path that alternates between unmatched and matched edges and whose two ends are both free; swapping its edges grows the matching by one. The search follows the length-3-path oracles of Beating Greedy Matching in Sublinear Time and A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time, extended to length $O(1/\epsilon)$.

The crux is a charging lemma. The lemma must show that if a round spends many queries without finding augmenting paths, then the edges it probed, sorted by round, form an ordered sequence of matchings. Each matching must be induced with respect to the earlier ones. This is the static analogue of the certification argument in Behnezhad–Ghafari. In their dynamic version, the induced structure comes from the order in which edges arrive. In ours, it must come from the random greedy order together with the round structure. We expect this to be the main difficulty and the most likely point of failure.

The third stage is a matching-model audit. The quadratic lower bound is proved for adjacency-list queries, so the algorithm must live in exactly that model. The audit must also check that the hard instance family, the hierarchical camouflage distribution, is not excluded by any structural assumption the algorithm uses.

There are two fallbacks, each publishable on its own if the main lever fails.

The first fallback is the obvious version of Gap 1 in the file: conditional query lower bounds for intermediate ratios. One would hide planted matchings among the induced matchings of a dense Ruzsa–Szemerédi graph, and show that $(2/3-\epsilon)$ or $(1.5+\epsilon)$-type estimation needs $n^{1+\Omega(\log RS(n)/\log n)}$ queries. This targets the exponent gap left open by the $n^{1.2-o(1)}$ lower bound for $(2/3+\epsilon)$-approximation in Sublinear Time Algorithms and Complexity of Approximate Maximum Matching, measured against the $n^{2-\Theta(\epsilon^2)}$ upper bound in Sublinear Algorithms for (1.5+ε)-Approximate Matching.

The second fallback is weaker. One would read the camouflage construction directly, extract the ordered induced matchings it implicitly contains, and see whether they already give a density bound.

Baselines

The naive reference point is reading the whole graph and computing an exact maximum matching. That costs $O(m)$ adjacency-list queries, up to $n^2$. Any lever result needs a cost strictly below this, expressed in terms of ORS density. Otherwise the inequality above carries no information.

The strongest existing method for near-optimal static estimation is the same full-read baseline. The file records no strongly subquadratic $(1,\epsilon n)$ estimator, and the quadratic lower bound says none exists without dependence on $\epsilon$. We will therefore report the comparison as an exponent of $n$ at fixed $\epsilon$.

For constant-factor ratios, the strongest competitors are the following. Randomized greedy reaches $(2,\epsilon n)$ in $O(\bar d/\epsilon^2)$ adjacency-list time (Time-Optimal Sublinear Algorithms for Matching and Vertex Cover). Mahabadi–Roghani–Tarnawski reach 0.5109 in $\tilde O(n^{1.5})$. Bhattacharya–Kiss–Saranurak use edge-degree constrained subgraphs, sparse subgraphs that cap the summed degrees of each edge's endpoints, to reach $1.5+\epsilon$ in $n^{2-\Theta(\epsilon^2)}$.

In empirical runs, all methods get the same graph access, counted in identical query units, and the same budget sweep. Each baseline's $\epsilon$ is tuned over the same grid.

The key ablation isolates the charging lemma. We run the same augmenting-path rounds with fresh random orderings each round, with no greedy pseudo-history. If the induced ordering in the recorded probes disappears, then the pseudo-history is what produces the ORS structure.

Beating the baselines has two meanings, one for each part of the work. On the theory side, it means proving the bound $Q \le n^{1+o(1)}\text{ORS}^c$. On the empirical side, it means reaching lower additive error than the 0.51 and edge-degree-subgraph estimators at equal query budgets.

Why not just…?

Why not just prove conditional lower bounds from Ruzsa–Szemerédi density, as Assadi did for streaming? This is our first fallback and it is worth doing. However, it only assumes the conjecture. It can never say anything about whether the conjecture is true. At the $(1-\epsilon)$ end it also adds nothing, because an unconditional quadratic bound already exists there. The lever is the only route on the table that turns existing hardness into combinatorial knowledge.

Why not just simulate the Assadi–Khanna dynamic algorithm statically, inserting the graph's edges one at a time? This is the obvious transfer. It costs $m\cdot n^{o(1)}\text{ORS}(n)$, which is at least the full-read baseline, so the inequality yields nothing. The point of the proposal is to replace the update sequence with something costing $\tilde O(n)$. We will explicitly check whether a randomized greedy order can do that job.

Why not just attack ORS density combinatorially, by constructing dense ordered induced matchings directly? That is the path that has stalled. The files bound ORS density only between $n^{o(1)}$ and $n^{1-o(1)}$, and Behnezhad–Ghafari's Open Problem 2 asks whether ORS density is polynomially bounded by Ruzsa–Szemerédi density. This is a real alternative, not a straw man. Our small-$n$ search below is a cheap probe of it. A successful algorithmic lever would side-step it entirely.

Proposed Experiments

The decisive check is theoretical: either the charging lemma holds in the adjacency-list model, or we find a concrete instance where probes fail to form ordered induced matchings.

Empirical work supports this in three ways.

First, we implement the algorithm and instantiate the hierarchical camouflage distribution from Approximating Maximum Matching Requires Almost Quadratic Time at feasible $n$, roughly $10^3$ to $10^5$. On each instance we record the probed edges, greedily extract the longest ordered induced-matching sequence, and plot its length against total queries. The lemma predicts the relation $Q \approx n\cdot \text{length}^c$. A flat or superpolynomial gap falsifies the approach early.

Second, we run all baselines on SNAP graphs (SNAP: A General-Purpose Network Analysis and Graph-Mining Library), measuring additive error against exact matching size as a function of queries. No reported result was found on Lacuna for empirical matching-size estimation error on SNAP. The theoretical reference points are the bounds stated in the Baselines section.

Third, an integer-programming search for maximal ORS graphs at $n \le 40$ gives a weak sanity check on whether ordered inducedness is strictly less restrictive than ordinary inducedness at small scale.