On the Maximum Number of Edges in a Hypergraph with Given Matching Number

Peter Frankl

Source-linked AI summary

On the Maximum Number of Edges in a Hypergraph with Given Matching Number

Peter Frankl

arXiv:1205.6847v1May 30, 2012math.CO

TL;DR

The paper addresses the Matching Conjecture for uniform hypergraphs, proving its k = 3 case. It uses reductions to stable families and selected finite checks, with the stated result that the conjecture holds for k = 3.

Problem
The paper addresses the problem of determining the maximum size of a uniform hypergraph with a fixed matching number, framed through the Matching Conjecture.
Source: §2 · p. 3, §3 · p. 4
Method
The proof reduces to stable families and establishes Conjecture 3.1 for k = 3 at selected pivotal values of n.
Source: §2 · p. 2, §3 · p. 4
Results
The Matching Conjecture is true for k = 3.
Source: §1 · p. 1
Takeaways & Limitations
Conjecture 3.1 would imply Erdős’ Conjecture 1 for s ≥ k.
Source: §3 · p. 4
The paper reports that its general-k results fall short of a full proof of the Matching Conjecture.
Source: §13 · p. 25

Abstract

from arXiv · show

The aim of the present paper is to prove that the maximum number of edges in a 3-uniform hypergraph on n vertices and matching number s is max{\binom(3s+2,3), \binom(n,3) - \binom(n-s,3)} for all n,s, n >= 3s+2.

1. Introduction

The paper targets the Matching Conjecture for 3-uniform hypergraphs, and states that the conjecture holds for k = 3. Its notation and tools reduce the extremal problem to a finite family comparison, although the text notes that checking all families is impractical.

1. Introduction

Earlier work established the conjecture for sufficiently large n, with successive improvements to the threshold n0(k,s).The passage reports bounds by Bollobás, Daykin and Erdős, Huang, Loh and Sudakov [HLS a], and Füredi and the author.Source: §1 · p. 1
The paper states that the Matching Conjecture is true for k = 3.The introduction identifies proving this case as the paper’s aim.Source: §1 · p. 1
For n = k(s+1), the conjectured bound reduces to |F| ≤ |A1|, a case proved implicitly by Kleitman.The s = 1 case is the Erdős–Ko–Rado Theorem [EKR61].Source: §1 · p. 2

2. Notation, tools

The argument assumes stable families, since the cited result says it is sufficient to prove the conjecture for that class (cf.).The paper uses stability throughout.Source: §2 · p. 2
For fixed k and s, Formula 2.2 reduces the maximum-size problem to comparing families on [ks+k−1], but the number of families makes exhaustive checking impractical.The paper introduces particular families after noting this practical obstacle.Source: §2 · p. 3

3. Preliminaries

The preliminaries set up a partition-based framework and reduce the k = 3 proof to establishing Conjecture 3.1 at selected values of n. That conjecture, if proved, would imply Erdős’ Conjecture 1 for s ≥ k.

3. Preliminaries

The framework fixes a partition F0 ∪ F1 ∪ ··· ∪ Fs = [ks+k−1], with F1,…,Fs drawn from F.F0 is chosen lexicographically first among eligible (k−1)-element sets, and the Fi are then selected accordingly.Source: §3 · p. 3
Every eligible tuple preceding (d1,…,dℓ) lexicographically belongs to F0 for 1 ≤ ℓ < k.This is Proposition 3.1, derived using maximality of F.Source: §3 · p. 3
For a tuple R of indices, the paper restricts F0 to X(R) to form H(R), then defines width and weight for the ensuing comparisons.The supplied passages identify these objects and definitions but do not provide their complete formulas.Source: §3 · p. 4
The value f(ℓ) is independent of the particular choice of R, and the paper uses this common value in Conjecture 3.1.The paper then focuses on establishing that conjecture for k = 3 at the two specified n values.Source: §3 · p. 4
For k = 3, the proof establishes Conjecture 3.1 at n = n0(s,3) and n = n0(s,3)−1 as the route to Theorem 1.1.The passage says these are the required values and that Conjecture 3.1 would imply Erdős’ Conjecture 1 for s ≥ k.Source: §3 · p. 4
The later proof sections handle s = 2, then s ≥ 4, and finally the remaining case s = 3 for k = 3.Sections 9–11 establish the required inequality in the range that settles s ≥ 4.Source: §3 · pp. 4–5

4. Some easy facts

The section establishes structural constraints on restricted families H(R), including their matching number and restrictions on which triples can occur. These facts support later comparisons of their total weights with the reference families A3 and A2(n).

4. Some easy facts

For R of size p, H(R) has matching number exactly p.The p matching edges come from the selected Fi, while the other s−p edges remain disjoint from H(R), forcing the reverse bound.Source: §4 · p. 5
When d1 = 1, the pairs (ai,ci) and (bi,ci) are excluded from F0; if (ai,bi) is present, (1,ci) is excluded too.These restrictions follow from ν(H({i})) = 1.Source: §4 · p. 5
If (d1,xi) belongs to F0, then replacing xi in Fi by d2 does not produce a set in F0.Source: §4 · p. 5
For edges Fu and Fv of the special matching, ai(u) < ak(v).The proof uses stability to replace the two edges with alternatives that contradict the chosen special matching.Source: §4 · p. 5
The later comparisons measure extra edges as losses and missing reference edges as gains, combining their weights into a balance against A3 or A2(n).For k = 3, G denotes the members of F0 of size 2.Source: §4 · pp. 5–6

5. Why induction would work

This section develops an induction strategy by reducing the cases that need checking and deriving constraints on a minimal counterexample. In particular, the k = 3 conjecture need only be checked at two pivotal values of n.

5. Why induction would work

Any minimal counterexample must satisfy ν(F(¯1)) = s.If ν(F(¯1)) = s−1, minimality and a bound on the subfamily containing 1 show F is not a counterexample.Source: §5 · p. 7
For a minimal counterexample, ν(F(¯1)) = s is the necessary case the induction argument must address.The section explains that one may assume this condition when formulating an inductive proof.Source: §5 · p. 7
If the conjecture holds for (n−1,k−1,s) and (n−1,k,s), with A1(n−1) maximal in the latter, it holds for (n,k,s) with A1(n) maximal.This is the induction step stated in Proposition 5.2.Source: §5 · p. 7
The pivotal number n0(s,k) is the least n for which |Ak| ≤ |A1(n)|, and the section establishes n0(s,k) < (k+1)s.Source: §5 · p. 7
To prove Conjecture 1 for k = 3, it is sufficient to establish it for n = n0(s, 3) and n = n0(s, 3) − 1.Source: §5 · p. 8

6. The structure of H(i, j)

The section classifies the possibilities when |H2| is large and uses the matching-number constraint to rule out several candidate sets. In each case, stability yields further missing sets in H(i, j).

6. The structure of H(i, j)

When |H2| ≥3, Proposition 6.1 restricts the structure to one of three cases.The supplied passages do not specify the full alternatives.Source: §6 · p. 8
In cases (i) and (ii), five specified width-2 sets are missing from H(i, j).These include {xi, d, cj} for xi ∈ Fi, as well as (aj, d, ci) and (bj, d, ci).Source: §6 · p. 8
In case (iii), six sets {xi, yj, d} of width 2 are missing, with xi = bi or ci and yj ∈ Fj.The proof reduces the claim to excluding {bi, aj, d} using ν(H(i, j)) = 2.Source: §6 · p. 8
Among nine candidates in each of two classes, fewer than half are actually in H(i, j), a restriction used toward Conjecture 1.Source: §6 · p. 8

7. Some important special cases

This section develops structural conditions on H(R), including normality, fatness, and robustness. These conditions constrain missing transversals, edge sizes, and the number of width-2 sets when k = 3.

7. Some important special cases

A missing diagonal implies that at least k! transversals are also missing from H(R).There are k! transversals T satisfying D ≪ T for every diagonal D.Source: §7 · p. 9
If all k! diagonals belong to H(R), then R is normal, with the smallest elements assigned successively to T1, T2, and onward.Source: §7 · p. 9
If H(R) is not fat, at least (k −1)^(k−1) transversals are missing from H(R).The proof partitions the transversals in T2 ∪· · ·∪Tk into groups and shows each group contains a missing transversal.Source: §7 · p. 9
If R is both fat and normal, every H ∈ H(R) contained in Fi1 ∪· · ·∪Fik has size k.Fatness here means k −1 disjoint members of H(R) cover T2 ∪· · ·∪Tk.Source: §7 · pp. 9–10
For k = 3, robustness implies that H1 ∪· · ·∪Hk = T1 ∪T2 for the sets specified in Claim 7.2.Robustness is defined by k pairwise disjoint members of H(R), each of size k −1.Source: §7 · p. 10
For a non-robust triple R = {u, v, z}, the number g2 of width-2 sets in H(R) is at most 9.Source: §7 · p. 11

8. The case s = 2

For s = 2, the section uses constraints on a family F and on width-2 sets in H(1, 2) to establish the case. It identifies a family satisfying (8.2) and derives bounds on g1 and g2.

8. The case s = 2

The section derives g1 ≤6 and g2 ≥3 for the width-2 sets under consideration.It also uses g1 + g2 ≥9 and g2 = 3 to infer g1 ≥6.Source: §8 · p. 12
Every F ∈ F intersects {1, a1, a2, b1, b2} in at least two elements.This is the stated condition (8.2).Source: §8 · p. 12
The family satisfying (8.2) is exactly F2(10) and has size 25.Source: §8 · p. 12

9. Fat and sufficiently fat triples

The section compares H(R) with a complete 3-graph and distinguishes fat, non-fat, and sufficiently fat triples. These structural cases yield bounds on missing edges and on the size of a family of width-3 sets.

9. Fat and sufficiently fat triples

For a fat triple R, the section establishes inequality (3.3).Source: §9 · p. 12
If R is not fat, at least 4 width-3 sets and 6 width-2 sets are missing from H(R).Source: §9 · p. 13
If |Q| is 3, 2, or 1, respectively, the specified excluded pairs are (ai, aj), (ai, ak), or (aj, ak).Source: §9 · p. 14
If R is not sufficiently fat, |T| ≤20 and at least 12 edges from F2 ∩ H(R) are missing.Here T is defined as F3 ∩ H(R).Source: §9 · p. 14
When |Q| = 1, |F| ≤21 and at least 10 edges from F2 ∩ H(R) are missing.Source: §9 · p. 15

10. Sufficiently fat is sufficient

For sufficiently fat triples, the proof establishes (3.3) by bounding losses against gains, with cases divided by |Q|. The |Q| = 2 case has one exception, while the |Q| = 3 case is settled.

10. Sufficiently fat is sufficient

The argument estimates maximal losses from above and identifies basic gains; when |G2 ∩ H(u, v)| ≥ 3, it can use Corollaries 6.1 and 6.2 for additional gains.Source: §10 · p. 16
For |Q| = 3, (3.3) holds.Proposition 10.1 handles this case directly.Source: §10 · p. 16
For |Q| = 2, (3.3) holds except when s = 3 and n = 13.That exceptional case is deferred to Section 12.Source: §10 · p. 17
The remaining inequalities are checked in small cases and extended to larger s by monotonicity.The proof concludes Proposition 10.3 after treating its stated cases.Source: §10 · pp. 17–18

11. Not sufficiently fat is sufficient

For triples that are not sufficiently fat, the proof establishes (3.3) when g2 ≤ 9 and s ≥ 4. It treats the small s = 4 cases separately and reserves s = 3, n = 13 for Section 12.

11. Not sufficiently fat is sufficient

For fixed g2, the reformulated inequality has a constant right side and a left side decreasing with s.Thus, once it holds at s = 6, it holds for all s ≥ 6.Source: §11 · p. 19
For g2 ≥ 7, the proof adds gains when some G2 ∩ H(u, v) contains at least three elements.The added gains support the adjusted inequality, which then extends by monotonicity.Source: §11 · p. 20
For a triple that is not sufficiently fat and g2 ≤ 9, (3.3) holds for s ≥ 4.This is Proposition 11.1; the proof separately handles s = 4.Source: §11 · p. 20
The s = 3, n = 13 case is left for direct treatment in Section 12.The passage explains that the induction can be supported without proving the bound at this exceptional case.Source: §11 · p. 20

12. The last case

The final case treats s = 3, n = 13 directly, assuming a counterexample of size at least 166 and deriving incompatible bounds. The argument builds constraints on missing sets and on the families G1 and G2.

12. The last case

The proof derives g1 + g2 ≥ 15, then shows either g2 ≤ 8 or (1, b1) ∉ G1.Together with the indirect assumption |F| ≥ 166, this yields a contradiction.Source: §12 · pp. 21–22
The passage shows either g2 ≤ 8 or (1, b1) ∉ G1, then plugs g1 + g2 ≤ 17 into (12.1) while indirectly assuming |F| ≥ 166.Source: §12 · p. 22
Finally, Corollary 12.5 and Claim 12.10 provide 33 missing sets; using (12.1) and |G| = 15, the argument proceeds toward a contradiction.Source: §12 · p. 24
The proof establishes further structural constraints, including that at most five missing triples contain 1 or 2.It also derives specific membership and non-membership claims for edges in G and triples in F1.Source: §12 · pp. 21, 23, 24

13. Uniqueness and beyond

For stable families, the proof characterizes equality cases; the paper also states a k = 4 result for sufficiently large s. It does not give a full proof of the Matching Conjecture.

13. Uniqueness and beyond

For stable families, equality in the maximum-size bound is possible only for F = A3 or F = A1(n).In the equality case, F is isomorphic to F(G).Source: §13 · pp. 24–25
In case of equality, F = F3 or F = F2(n).The same result holds for s = 2, 3, and 4, but requires more detailed case analysis or a different proof.Source: §13 · p. 25
For k = 4 and s > s0, the paper states that the Matching Conjecture is true.The paper says its general-k results do not amount to a full proof of the Matching Conjecture.Source: §13 · p. 25