Source-linked AI summary
Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels
Noga Alon, Peter Frankl, Hao Huang, Vojtech Rodl, Andrzej Rucinski, Benny Sudakov
TL;DR
The paper asks when minimum d-degree guarantees perfect integral or fractional matchings in uniform hypergraphs. It reduces the problem to extremal bounds related to Erdős’ conjecture and proves special cases using probabilistic and absorbing methods. The results establish asymptotic threshold conclusions, including new instances for uniformities three and four that yield matching-threshold consequences.
Problem
The paper studies conditions ensuring perfect matchings and perfect fractional matchings, focusing on the relation between minimum d-degree and matching numbers.
Method
The paper reduces threshold estimates to fractional matching extremal problems, proves selected cases with probabilistic techniques, and uses an absorbing lemma to convert almost perfect fractional structure into integer matchings.
Results
Theorems 1.1–1.3 establish asymptotic equality of integral and fractional thresholds under a stated condition and confirm the fractional conjecture for l = 3,4, yielding new instances of the integral conjecture.
Takeaways & Limitations
The results provide general minimum-degree criteria for perfect matchings and perfect fractional matchings, with applications to optimal data allocation in distributed storage.
Takeaways & Limitations
The precise fractional conjecture is false for non-integer s, and the probabilistic method has stated range limits for larger fractional matching parameters.
Abstract
from arXiv · showhide
In this paper we study conditions which guarantee the existence of perfect matchings and perfect fractional matchings in uniform hypergraphs. We reduce this problem to an old conjecture by Erdős on estimating the maximum number of edges in a hypergraph when the (fractional) matching number is given, which we are able to solve in some special cases using probabilistic techniques. Based on these results, we obtain some general theorems on the minimum $d$-degree ensuring the existence of perfect (fractional) matchings. In particular, we asymptotically determine the minimum vertex degree which guarantees a perfect matching in 4-uniform and 5-uniform hypergraphs. We also discuss an application to a problem of finding an optimal data allocation in a distributed storage system.
1 Introduction
The paper studies minimum d-degree thresholds for perfect and perfect fractional matchings in uniform hypergraphs. It connects these thresholds to extremal bounds on hypergraphs with prescribed matching numbers and proves several asymptotic cases.
- Problem: The paper relates minimum d-degree δd(H) to the integral matching number ν(H) and fractional matching number ν∗(H).Perfect matchings have size |V|/k, while perfect fractional matchings have fractional matching number n/k.
- Problem: The main objective is to determine the asymptotic behavior of md(k,n) and fd(k,n) for fixed k and d as n tends to infinity.These parameters govern when minimum d-degree guarantees matchings of a prescribed size, especially perfect matchings.
- Main results: If fd(k,n) ∼ c∗n^-d for some c∗ > 0, then md(k,n) and fd(k,n) are asymptotically equal.This reduces the integral threshold problem to estimating the fractional threshold.
- Main results: For every k ≥ 3 and k−4 ≤ d ≤ k−1, the paper confirms the relevant fractional threshold conjecture asymptotically.Together with the comparison theorem, this yields new instances of the corresponding integral matching conjecture.
2 Fractional matchings and probability of small deviations
The section reduces fractional Erdős bounds to Samuels’ probabilistic conjecture on sums of independent random variables, proving the needed cases and identifying the method’s range of validity.
- Probabilistic reduction: The paper uses a probabilistic approach based on a special case of Samuels’ conjecture to prove fractional Erdős-type bounds.The argument converts a fractional vertex cover into independent random variables and estimates small-deviation probabilities.
- Samuels’ conjecture: For l ≤ 4, Samuels’ conjecture holds, and equal expectations attain the minimum at Q0 = (1 − x)^l when x ≤ 1/(l + 1).The equal-expectation statement is established through Proposition 2.1 and its supporting inequalities.
- Fractional Erdős bounds: For l = 3 and x ≤ 1/4, and for l = 4 and x ≤ 1/5, the maximum edge count under fractional matching number less than xm is bounded asymptotically.Theorem 2.1 transfers the probabilistic conjecture to the fractional Erdős problem.
3 Thresholds for perfect fractional matchings
This section derives thresholds for perfect fractional matchings by reducing minimum d-degree questions to fractional matching bounds in neighborhood hypergraphs. The resulting framework connects Samuels-type estimates to threshold results.
- Reduction to neighborhood graphs: If a k-graph has no fractional perfect matching, a d-set of minimum-weight vertices yields a neighborhood hypergraph with fractional matching number less than n/k.Fractional vertex-cover duality supplies the weight function and the reduced neighborhood graph.
- Threshold transfer: The neighborhood construction implies that a d-degree threshold can be bounded using the fractional Erdős quantity for a (k − d)-uniform hypergraph.The proof proceeds contrapositively: sufficiently large minimum d-degree forces a fractional perfect matching.
- Applications: For d = k − 1, the fractional threshold is immediate; for d = k − 2, k − 3, and k − 4, it follows from the corresponding fractional Erdős estimates.The cases use the l = 2 result and the corollary established in the previous section.
- Conditional extension: For identically distributed variables and l ≥ 5, the stated bound P(X1 + · · · + Xl < 1) ≥ (1 + o(1))(1 − x)^l would extend the threshold theorem to d = k − l.The paper presents this as a conditional extension based on the restricted Samuels problem.
4 Constructing integer matchings from fractional ones
The paper converts fractional matching information into an integer perfect matching through absorption and randomized sparsification. An absorbing matching handles the leftover vertices after an almost perfect matching is found.
- Absorption framework: The proof uses an absorbing matching, an almost perfect matching, and the absorber to complete a perfect matching.The three steps first reserve absorption capacity, then cover almost all vertices, and finally absorb the remainder.
- Almost perfect matching: A nearly regular subhypergraph with sufficiently smaller maximum 2-degree contains a matching covering all but at most εn vertices.This lemma supplies the almost perfect matching required by the absorption strategy.
- Randomized sparsification: Randomized sampling constructs a spanning subhypergraph with vertex degrees asymptotic to n^0.2 and maximum 2-degree at most n^0.1.The construction uses repeated random vertex sets, concentration inequalities, and edge-disjoint induced subhypergraphs.
- Completion: The resulting almost perfect matching covers at least (1 − ε)|V(H′)| vertices, enabling the absorber to finish the perfect matching.This establishes the intermediate matching needed in Step 2 of the proof.
- Rounding fractional matchings: Fractional perfect matchings in the sampled subhypergraphs are independently rounded to produce the desired degree and codegree bounds.The resulting generalized binomial subhypergraph has vertex degrees asymptotic to n^0.2 and pair degrees at most n^0.1 with high probability.
5 An application in distributed storage allocation
The paper reformulates optimal distributed-storage allocation as maximizing the probability of successful recovery under a fixed total allocation. This optimization is asymptotically connected to extremal hypergraphs with bounded fractional matching number, yielding clique- or complement-of-clique-based allocations.
- Problem: The storage problem seeks an allocation (x1, · · ·, xn) with total budget T that maximizes successful file recovery.The file is redundantly stored across n nodes, and recovery is possible when the accessed nodes contain at least one unit of data.
- Problem: For T ≥ n/r, setting all xi = T/n ≥ 1/r allows recovery from every subset of r nodes.In this regime, the optimal recovery probability is 1.
- Hypergraph reformulation: The optimization equals the maximum edge count in an r-uniform hypergraph on n vertices with fractional matching number at most T.Threshold hypergraphs encode r-subsets whose assigned node weights sum to at least 1, linking storage allocations to fractional matchings.
- Connection to extremal theory: The storage optimization is asymptotically equivalent to the fractional Erdős problem, whose analysis uses the Erdős–Gallai theorem in the discussed range.The paper relates the maximum-probability formulation to F^T(r,n), the maximum number of edges under a fractional matching constraint.
- Extremal allocations: For T < 2n/5, an optimal allocation is x1 = · · · = xT = 1 and xT+1 = · · · = xn = 0.For the other stated regime, the paper gives x1 = · · · = x2T = 1/2 and the remaining allocations equal to zero.
- Extremal allocations: The extremal bounds are achieved by a clique or a complement of a clique, producing two corresponding asymptotically optimal allocation patterns.The clique allocation assigns 1/r to rT nodes and zero elsewhere; the complement-of-clique allocation assigns 1 to T nodes and zero elsewhere.
6 Concluding Remarks
The paper derives minimum-degree conditions for perfect and perfect fractional matchings by studying fractional matching thresholds and related extremal conjectures. It also identifies open conjectures and connects the theory to distributed-storage allocation.
- Main conclusions: The paper studies sufficient minimum d-degree conditions guaranteeing perfect matchings or perfect fractional matchings in uniform hypergraphs.Its approach uses asymptotic fractional matching thresholds to determine perfect-matching thresholds in selected cases.
- Main conclusions: The minimum vertex degree threshold for perfect matchings is asymptotically determined in the paper’s highlighted 5-uniform case.The supplied conclusion states this result through the asymptotic behavior of m1(5,n).
- Open problems: The full Erdős conjecture on the maximum edge count under a matching-number constraint remains open.The conjecture asserts an exact extremal edge count for k-uniform hypergraphs with matching number smaller than s.
- Open problems: The fractional Erdős conjecture is related to a probabilistic conjecture of Samuels, whose proof would resolve the fractional problem in a stated range.The paper further states that this would yield asymptotics for md(k,n) and fd(k,n) for arbitrary k ≥ d + 1 and d ≥ 1.
- Application: The distributed-storage allocation model leads to a question asymptotically equivalent to the fractional Erdős problem.The paper notes that the accessed nodes may instead be sampled independently with probability p, suggesting a further direction for the techniques.