Source-linked AI summary
The size of a hypergraph and its matching number
Hao Huang, Po-Shen Loh, Benny Sudakov
TL;DR
The paper studies the range in which Erdős’s conjecture determines the maximum size of a k-uniform hypergraph with matching number below t. Using shifting and a degree-based argument, it verifies the conjecture for t < n/(3k^2), improving the previously known range by a factor of k.
Problem
Erdős’s conjecture asks when the extremal bound is attained for k-uniform hypergraphs whose matching number satisfies ν(H) < t.
Method
The proof uses shifting and analyzes the t-th largest degree, with the argument already complete when that degree exceeds 2t.
Results
The conjecture is verified for t < n/(3k^2), improving the previously best-known range by a factor of k.
Takeaways & Limitations
The verified range extends the known validity of Erdős’s conjecture toward the conjectured general range.
Takeaways & Limitations
The paper leaves open tightening the verified range to t < O(...).
Abstract
from arXiv · showhide
More than forty years ago, Erdős conjectured that for any T <= N/K, every K-uniform hypergraph on N vertices without T disjoint edges has at most max{\binom{KT-1}{K}, \binom{N}{K} - \binom{N-T+1}{K}} edges. Although this appears to be a basic instance of the hypergraph Turán problem (with a T-edge matching as the excluded hypergraph), progress on this question has remained elusive. In this paper, we verify this conjecture for all T < N/(3K^2). This improves upon the best previously known range T = O(N/K^3), which dates back to the 1970's.
1 Introduction
The paper studies Erdős’s conjecture on the maximum size of a k-uniform hypergraph with matching number below t, proving it in an expanded parameter range through a degree-based and multicolored matching argument.
- Problem: The conjecture asks for the maximum number of edges in a k-uniform hypergraph with matching number ν(H) < t, with two competing extremal constructions.The constructions are a clique on kt−1 vertices and all edges intersecting a fixed set of t−1 vertices.
- Prior work: Earlier work established only partial ranges, including asymptotic results and bounds depending on n and k.Known cases included t = 2, graphs, fixed t and k for sufficiently large n, and selected ranges for 3-uniform hypergraphs and general k.
- Main result: The paper proves Erdős’s conjecture for t < n/(3k^2), extending the range in which the conjectured maximum is verified.The theorem applies to every k-uniform hypergraph on n vertices without t disjoint edges.
- Multicolored extension: This degree insight leads to a multicolored Erdős conjecture about rainbow matchings across t set families.The paper proves an asymptotic version and uses it to establish the main theorem, while also obtaining the multicolored conjecture in the same parameter range.
2 Shifting
This section introduces shifting as a structure-preserving tool for extremal set families and combines it with decomposition and induction. The resulting lemmas preserve uniformity, size, and the absence of pairwise disjoint choices, including under a decomposition by the final element.
- Shifting: Shifting preserves family size, uniformity, and the property that no selected sets are pairwise disjoint.The shift replaces i by j only when the resulting set is not already present, and the stated lemma establishes these three preservation properties.
- Shifting: The (i, j)-shift moves a set F to F \ {i} ∪ {j} exactly when i belongs to F, j does not, and the replacement is absent.
- Shifting: After shifting successively toward the final element n, each family is split into sub-families according to whether n is contained.This decomposition is used together with induction on the number of elements in the underlying set.
- Shifting: The rainbow matching number does not increase under this decomposition.For shifted families satisfying the no-pairwise-disjoint-selection condition, the corresponding sub-families retain that condition.
- Shifting: The preservation under decomposition follows by replacing sets containing n with sets using distinct elements outside the union of the selected sets.Shift invariance supplies the replacement sets, yielding a contradiction if the decomposed families admitted pairwise disjoint choices.
3 Main result
The paper proves Erdős’s matching conjecture for t < n/(3k^2) and extends the argument to multicolored families, guaranteeing disjoint representatives under analogous size conditions.
- Proof strategy: A multicolored matching lemma underlies the extension, using shifts, induction, and partitioning families according to whether sets contain a designated vertex.The shifted families preserve the relevant disjointness property, enabling induction on the number of vertices and set sizes.
- Supporting lemma: The degree-based corollary shows that t vertices each having sufficiently large degree force t disjoint edges when kt ≤ n.The proof converts edges through selected vertices into (k−1)-uniform families and applies the multicolored lemma.
- Theorem 1.2: For t < n/(3k^2), every k-uniform hypergraph exceeding the conjectured edge bound contains t disjoint edges.The proof proceeds by induction on t, splitting according to maximum vertex degrees and using degree-counting arguments.
- Proof strategy: The proof handles a high-degree vertex by finding t−1 disjoint edges away from it and then selecting an additional incident edge avoiding their vertices.When maximum degree is bounded, the argument instead controls degree sums on vertices covered by t−1 edges to force another disjoint edge.
- Multicolored extension: The multicolored extension states that k-uniform families with t < n/(3k^2) and each size above the corresponding threshold contain pairwise disjoint representatives.Theorem 1.2 is recovered when all families coincide.
4 Concluding Remarks
The paper verifies Erdős’s conjecture for t < n/(3k^2), improving the previous range by a factor of k. The concluding remarks also identify related fractional and multicolor questions and a remaining goal of extending the range.
- 4 Concluding Remarks: For t < n/(3k^2), every k-uniform hypergraph with matching number less than t has at most the conjectured number of edges.This verifies Erdős’s conjecture in the stated range.
- 4 Concluding Remarks: The result improves the previously best-known range by a factor of k.
- 4 Concluding Remarks: Tightening the verified range remains an open direction.The paper specifically notes interest in reaching t < O(...).
- 4 Concluding Remarks: The fractional version of Erdős’s conjecture connects hypergraph edge bounds to probability and distributed data-allocation problems.
- 4 Concluding Remarks: The paper proposes a multicolor analogue asking for the maximum product of family sizes when no t pairwise disjoint choices exist.