A hypergraph generalizes a graph by letting each edge join $k$ vertices instead of two. A perfect matching in such a hypergraph is a set of disjoint edges that covers every vertex exactly once. For $k \ge 3$, deciding whether one exists is NP-complete. Extremal combinatorics nonetheless proves that a perfect matching must exist once the hypergraph is dense enough, for example when every $(k-1)$-set of vertices lies in more than about $n/2$ edges. These existence proofs almost always follow one recipe. First set aside a small "absorber," a structure flexible enough to swallow any small set of leftover vertices. Then cover almost everything else with a random or greedy packing. Finally let the absorber take whatever is left. The recipe is powerful. In practice it cannot be run: the absorber's capacity is tiny, and the bulk step typically uses the regularity lemma, whose constants make the required $n$ astronomically large.
We propose to turn this recipe into an algorithm that runs on real instances. The central change is to stop treating the bulk packing and the absorber as independent stages. We run the bulk packing as an iterative partial-coloring process, which fixes a small random fraction of the matching each round in the style of the Rödl nibble. We steer that process with discrepancy-style rebalancing, so that the leftover it produces is shaped to fit the absorber's actual capacity. The claim is that this coupling allows much smaller absorbers and much smaller degree slack above the extremal threshold. The result would be a randomized polynomial-time algorithm that finds the guaranteed perfect matching at sizes that can be tested, for $n$ in the thousands to tens of thousands, and whose success frontier can be measured against the known thresholds.
Core Claim
Standard absorbers are built to handle any small leftover set. Guaranteeing that worst case is what forces the absorber to be large relative to the leftover, and hence forces huge $n$. The leftover need not be arbitrary, though, because we control the process that produces it. Fix an absorber made of vertex-disjoint constant-size gadgets. Each gadget $g$ is a small matching such that, for a specific family of $k$-sets $S$, the vertices $V(g) \cup S$ also have a perfect matching. Once the bulk packing stops, the leftover $R$ has to be split into $k$-sets. Each $k$-set then has to be assigned its own distinct gadget that can absorb it. Absorption succeeds exactly when a Hall-type condition holds for the bipartite graph linking leftover $k$-sets to gadgets. Take any collection $\mathcal{T}$ of leftover $k$-sets, and let $N(\mathcal{T})$ be the set of gadgets able to absorb at least one of them. The condition is
$$|N(\mathcal{T})| \ \ge\ |\mathcal{T}| .$$
The textbook existence proof secures this for all $R$ at once through a union bound. We instead track, during the nibble, a load for each gadget: how many still-uncovered candidate $k$-sets currently depend on it. When a gadget's load drifts above its share, the partial-coloring step rebalances. It lowers the chance of freezing edges that would strand vertices whose only absorbers are overloaded. This is a discrepancy problem. The sets to be kept balanced are the gadget neighbourhoods, and the elements being colored are the candidate edges of the next round. The new ingredient is to use constructive discrepancy machinery to shape the residue of a matching process.
Where This Sits in the Literature
Three strands supply the pieces, and none has joined them. The absorbing side gives us the gadget definitions and the reduction from perfect to near-perfect matching. Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels proves a Strong Absorbing Lemma showing that perfect-matching thresholds track fractional-matching thresholds. Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II pins down exact $\ell$-degree thresholds for $k/2 \le \ell \le k-1$ using absorption plus stability analysis near extremal constructions. Minimum codegree condition for perfect matchings in k-partite k-graphs establishes the codegree threshold $n/2$ for even $k$ in the $k$-partite setting. All three choose absorbers by random selection plus a union bound. None gives an algorithm or an explicit $n_0$. We reuse their gadget definitions and target their thresholds, but we replace the worst-case union bound with process control.
The nibble side supplies the mechanism and its known limit. The distributed edge-coloring work in Near-Optimal, Distributed Edge Colouring via the Nibble Method shows that tentative choices with discard-on-conflict keep palettes concentrated. Improved Bounds for Coloring Locally Sparse Hypergraphs makes a hypergraph semi-random process algorithmic via the Moser–Tardos local lemma, but needs girth at least 5, which dense Dirac hypergraphs violate badly. That paper constrains our design. We do not try to run a coloring nibble on the hypergraph itself. We run a matching nibble, which is the Rödl–Pippenger setting where density helps rather than hurts. We also accept that concentration fails at the tail, which is exactly where the absorber takes over. Deterministic discrepancy walks, used for graph sparsification in Spectral Sparsification by Deterministic Discrepancy Walk and with hereditary guarantees in Fast Discrepancy Minimization with Hereditary Guarantees, supply the rebalancing step.
The closest bridge is Packing perfect matchings in random hypergraphs. It nibbles almost-spanning matchings in $H^k_{n,p}$ and then completes them with the Johansson–Kahn–Vu existence theorem used as a black box. The authors attribute their $\log^4(kn)$ slack partly to that step. Approximate generalized Steiner systems and near-optimal constant weight codes likewise obtains near-perfect matchings by nibble and asks outright for a constructive version (their Question 5.2). Both motivate the proposal. Our pipeline differs from Ferber–Vu in three ways. It is self-contained, since the completion is an explicit absorber rather than a theorem. It works on deterministic dense hypergraphs, not only random ones. And the nibble is aware of the completion step, instead of being blind to it.
One caveat about scope. The research file contains no polynomial-time algorithmic results for Dirac-threshold hypergraph matching, so we cannot say from this material how close existing algorithmic work comes to the thresholds. The first project task is a careful literature check on that point. The empirical contribution, measured success frontiers at finite $n$, stands regardless.
Research Program
We will build a solver for $k$-uniform hypergraphs, focusing on $k = 3$ and $k = 4$, that runs in four stages. First, a gadget census enumerates constant-size absorbing gadgets for random $k$-sets. The number of gadgets per $k$-set serves as a certificate of local absorbability. Second, the absorber is chosen as a vertex-disjoint gadget family by a greedy-plus-local-search procedure that maximizes the minimum gadget count over candidate $k$-sets. This replaces random selection with something we can inspect. Third, the steered nibble runs on the rest of the hypergraph. Each round samples a small fraction of candidate edges, discards conflicts, and freezes the survivors, with sampling weights adjusted by a multiplicative-weights or discrepancy-walk correction on gadget loads. Fourth, the leftover is split into $k$-sets and absorbed by solving a bipartite assignment, which is polynomial time. If assignment fails, the solver does a bounded local repair that swaps a few frozen edges back into the pool.
On the theory side, we aim to prove that above the codegree threshold with a slack of $\epsilon n$, the steered nibble leaves a leftover satisfying the Hall condition with high probability. We further aim to show that $n_0$ is polynomial in $1/\epsilon$ rather than tower-type. The source of the hoped-for polynomial dependence is that the argument uses only concentration over $O(\log(1/\epsilon))$ nibble rounds, with no regularity partition. Near extremal constructions, meaning the space and divisibility barriers surveyed in Recent advances on Dirac-type problems for hypergraphs, we do not claim success. There the solver is expected to hand off to a structure-detection branch that recognizes the barrier, following the stability case split of Treglown and Zhao.
Baselines
The naive reference point is greedy maximal matching followed by random restarts and bounded local augmentation, that is, swapping up to three edges to cover an unmatched vertex. For $k \ge 3$ there is no alternating-path theory, so we expect this to stall with a leftover that grows as density approaches the threshold. It gets the same wall-clock budget as our solver.
The exact reference point is a commercial-grade integer programming or SAT solver on the exact-cover formulation, given the same time limit per instance. It defines ground truth on small $n$ and shows where exact search stops scaling. Beating it means solving instances it times out on at the same budget, while matching its answers wherever it finishes.
The strongest method-level competitor is a faithful implementation of the unsteered absorbing pipeline from Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels, with a Ferber–Vu-style blind nibble for the bulk as in Packing perfect matchings in random hypergraphs. Its absorber is a randomly selected gadget family sized as the lemma prescribes, and its nibble has no load feedback. It shares our gadget enumerator, nibble rate, and absorber budget, and differs only in the steering and the absorber selection. No reported result was found on Lacuna for the empirical success rate of any absorbing or nibble pipeline on finite Dirac-type instances. The only quantitative anchors are theoretical: the thresholds themselves, and Ferber–Vu's edge-probability condition $p > \log^4(kn)/n^{k-1}$. Beating this baseline means one of two things. Either a strictly lower codegree ratio $\delta/n$ at which 95% of instances are solved, at equal $n$. Or the same success rate with an absorber at most half as large.
Two ablations isolate the key ingredient. The first turns off steering but keeps the optimized absorber. The second keeps steering but uses a random absorber. If the gain comes almost entirely from the absorber optimization, the discrepancy claim is wrong.
As a message-passing reference, belief propagation decimation is included. Planted matching problems on random hypergraphs reports BP succeeding for $k=3$ only above $\lambda_{alg} \approx 0.578$, against an information-theoretic threshold $\lambda_{it} \approx 0.43$.
Why not just…?
Why not just sample random gadgets and verify them, since absorbers in dense hypergraphs are constant-size? This is a real threat to one half of the idea. Choosing and checking an absorber in polynomial time is easy, so "derandomizing the absorber" alone is not a contribution, and we do not claim it is. The contribution lies in the interaction between absorber and nibble. A randomly sampled absorber of practical size has small capacity, and a blind nibble's leftover will often violate the Hall condition. The first ablation above, optimized absorber without steering, measures exactly how far sample-and-verify gets. If it matches the full method, we drop the steering claim.
Why not just solve the fractional-matching linear program and round it? Alon et al. show that fractional and integral thresholds coincide asymptotically only through an absorbing argument. Distributed Algorithms for Matching in Hypergraphs lists rounding fractional hypergraph matchings to integral ones as an open problem. Independent rounding leaves collisions and uncovered vertices, which is the same leftover problem again. We will include LP-guided nibble sampling as a variant, since it may be a better bulk step than uniform sampling. It still needs the absorber to finish.
Why not just hand the instance to a MIP or SAT solver? For small $n$ this will win, and we report that honestly. Its interest here is as ground truth. The question is scaling. Dirac-dense instances contain on the order of $n^{k-1}$ edges per vertex, so the formulation grows quickly. The exact-solver baseline shows where time-to-solution crosses our solver's polynomial curve.
Why not just use the vision hypergraph-matching solvers? Methods such as Adapt-BCAGM3 from An Efficient Multilinear Optimization Framework for Hypergraph Matching and HNN-HM from Hypergraph Neural Networks for Hypergraph Matching maximize a weighted correspondence score between two point sets. HNN-HM reports 68.0% accuracy on Pascal VOC. That task is a different problem: a bipartite assignment scored by third-order affinities, not an exact cover of an arbitrary $k$-uniform hypergraph. They are not competitors for exact spanning matchings, and we do not benchmark against them.
Proposed Experiments
The benchmarks are synthetic, because the file contains no public benchmark of dense Dirac instances. We will release a generator and fixed seeds. There are four instance families. The first is random $3$- and $4$-uniform hypergraphs conditioned on minimum codegree $\delta = cn$, with $c$ swept upward toward the threshold. The second is $4$-partite $4$-graphs with codegree swept around $n/2$, the exact threshold of Lu, Wang, and Yu. The third is $3$-graphs with adjacent-vertex degree sums swept around the roughly $0.6n^2$ threshold of Vertex degree sums for perfect matchings in 3-uniform hypergraphs. The fourth is perturbations of the space-barrier and divisibility-barrier constructions. We also run $H^3_{n,p}$ with $p$ swept down toward the matching threshold, to test whether self-contained absorption tolerates less slack than the $\log^4$ factor in Ferber–Vu's analysis.
Metrics are three: success probability of returning a verified perfect matching, runtime, and absorber size as a fraction of $n$. The headline plot is the 95%-success codegree ratio against $n$ for each method, for $n$ from 300 to roughly 30,000.
The decisive check is whether the gap between the steered and unsteered 95%-success ratios stays positive and grows as $n$ increases. If the steered frontier converges to the theoretical threshold while the unsteered one does not, leftover-shaping is doing real work. If the two coincide, the proposal reduces to a careful engineering of known ideas.
A second check runs the solver on planted $3$-uniform instances with $\lambda$ inside the hard phase $[0.43, 0.578]$. Finding some perfect matching is a different task from recovering the planted one, so success there would say nothing about the replica-symmetry-breaking barrier. Failure would suggest that density above the Dirac regime, not merely the existence of a matching, is what makes these instances tractable.
References
- Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels
- Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II
- Minimum codegree condition for perfect matchings in k-partite k-graphs
- Near-Optimal, Distributed Edge Colouring via the Nibble Method
- Improved Bounds for Coloring Locally Sparse Hypergraphs
- Spectral Sparsification by Deterministic Discrepancy Walk
- Fast Discrepancy Minimization with Hereditary Guarantees
- Packing perfect matchings in random hypergraphs
- Approximate generalized Steiner systems and near-optimal constant weight codes
- Recent advances on Dirac-type problems for hypergraphs
- Planted matching problems on random hypergraphs
- Distributed Algorithms for Matching in Hypergraphs
- An Efficient Multilinear Optimization Framework for Hypergraph Matching
- Hypergraph Neural Networks for Hypergraph Matching
- Vertex degree sums for perfect matchings in 3-uniform hypergraphs