PaperlayerView exact revision on arXiv

Source-linked AI summary

The Erd\H{o}s Matching Conjecture and concentration inequalities

Peter Frankl, Andrey Kupavskii

arXiv:1806.08855v3math.CO

TL;DR

The Erdős Matching Conjecture asks for the largest family of k-element sets with no s+1 pairwise disjoint members. The paper extends the conjecture’s proven range using a technical lemma on cross-dependent nested families. Its main theorem settles roughly one-third of cases left open by for sufficiently large s.

  • Problem

    The EMC asks for the maximum size of a family of k-element sets whose matching number is less than s+1, and conjectures that the maximum equals one of two candidate bounds.

    Source: §1 · p. 1

  • Method

    The proof uses a technical lemma on cross-dependent nested families, with Theorem 12 providing more control than a simpler averaging argument.

    Source: §4 · p. 9

  • Results

    Theorem 1 settles roughly one-third of the cases left open by, for sufficiently large s.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The EMC is connected to extremal combinatorics, probability questions about generalizations of Markov’s inequality, and computer-science questions.

    Source: §1 · p. 2

    The authors say new ideas are needed to prove the EMC for all n>(s+1)k.

    Source: §8 · p. 21

Abstract

from arXiv · show

More than 50 years ago, Erd\H os asked the following question: what is the maximum size of a family $\mathcal F$ of $k$-element subsets of an $n$-element set if it has no $s+1$ pairwise disjoint sets? This question attracted a lot of attention recently, in particular, due to its connection to various combinatorial, probabilistic and theoretical computer science problems. Improving the previous best bound due to the first author, we prove that $|\mathcal F|\le {n\choose k}-{n-s\choose k}$, provided $n\ge \frac 53sk -\frac 23 s$ and $s$ is sufficiently large. We derive several corollaries concerning Dirac thresholds and deviations of sums of random variables. We also obtain several related results.

1. Introduction

The Erdős Matching Conjecture asks how large a family of k-element sets can be if it contains no s+1 pairwise disjoint sets. This paper extends the range in which the conjecture is proved and develops a related universal bound.

1. Introduction

  • The EMC asks for the maximum size of a family F of k-element sets with matching number ν(F) < s+1.A matching is a collection of pairwise disjoint members of F.Source: §1 · p. 1
  • The conjecture says the maximum equals one of the two candidate bounds given by (2) and (3).The paper notes that the expression in (3) is independent of n.Source: §1 · p. 1
  • Earlier proofs established the conjectured bound for n≥2k^3s and n≥3k^2s, improving Erdős’s result for sufficiently large n.Source: §1 · p. 2
  • Theorem 1 settles roughly one-third of the cases left open by, for sufficiently large s.The theorem addresses part of the range (k+1)s < n < (2s+1)k−s.Source: §1 · p. 2

1.1. Bounds for the Erd˝os Matching Conjecture.

  • For 1<γ≤2−1/k, the paper gives a universal EMC bound when n≥γsk−(γ−1)s.This bound is weaker than (7) for roughly γ≤4/3 and stronger for γ≥4/3.Source: §1.1 · pp. 2–3
  • The proof of this bound uses Theorem 1 as a black box and relates Kneser-graph edge counts to the EMC.The result also has applications to Dirac thresholds.Source: §1.1 · p. 3

2. Preliminaries

The preliminaries establish that the EMC can be studied through initial families and develop shadow bounds for families with matching number at most s. They also introduce concentration of intersections with random full partitions as a key ingredient for the proof.

2. Preliminaries

  • When n = qk, a full partition of [n] into k-sets gives the bound (5), since at most s partition parts can belong to a family with matching number at most s.The argument also motivates studying intersections with randomly chosen full partitions.Source: §2 · p. 3
  • Concentration bounds for intersections with random full partitions are a new ingredient of the proof, using Kneser-graph eigenvalues with Chebyshev’s and Azuma–Hoeffding inequalities.The authors note that both bounds may be useful in other settings.Source: §2 · p. 3
  • Shifting preserves family size without increasing its matching number, so the EMC can be restricted to initial families.Initiality also rules out the set (s + 1, 2(s + 1), . . . , k(s + 1)) and yields a constraint on every family member.Source: §2 · pp. 3–4

2.1. Shadows of families satisfying ν(∂G) ≤s

  • Partitioning a family with ν(∂G) ≤ s by tail sets gives disjoint restricted shadows, which support improved lower bounds on shadow size.The argument improves an earlier bound slightly, and the authors say a more careful analysis is needed for Theorem 1.Source: §2.1 · pp. 4–5

3. Intersection of subsets and cliques in Kneser graphs is concentrated 

The section studies how many members of a family appear in a uniformly random matching of disjoint sets. It derives concentration bounds using Kneser-graph eigenvalues and martingale inequalities.

Intersection concentration

  • E[η] = αt for the number η of members of G in a uniformly random t-matching, and Lemma 10 gives a deviation bound via Chebyshev’s inequality.The setup assumes m ≥ tl and G is a family of l-sets from an m-element ground set.Source: §3 · p. 6
  • Kneser-graph eigenvalue properties bound the dependence between matching positions, yielding a Chebyshev concentration estimate for η.The argument estimates pairwise covariances using induced edges in the Kneser graph.Source: §3 · pp. 6–7

Martingale bound

  • Theorem 12 gives a stronger concentration bound by exposing the matching as a 2-Lipschitz martingale and applying Azuma–Hoeffding.The martingale starts at E[η] and ends at η.Source: §3 · pp. 7–8

4. Proof of Theorem 1

The proof establishes the EMC bound by induction, reducing the task to a threshold value of n and applying a lemma on cross-dependent, nested families. Random-matching concentration completes that lemma, yielding the theorem’s stated range.

4. Proof of Theorem 1

  • For sufficiently large s, Theorem 14 proves the EMC when n ≥ s + (1.666 + ε)s(k − 1), and this implies Theorem 1’s stated threshold.Theorem 1 follows by choosing ε < 5/3 − 1.666.Source: §4 · p. 9
  • Induction on k reduces the proof to n = s + (1.666 + ε)s(k − 1), with shiftedness providing the recurrence used to extend the result to larger n.The base case k = 3 is attributed to the first author.Source: §4 · p. 9
  • Lemma 15 is the key ingredient: for cross-dependent, nested families, it bounds a weighted sum of family sizes under its stated parameter conditions.The proof applies it to the sections F({i}) arising from the initial family.Source: §4 · pp. 9–10

4.2. Completing the proof of Lemma 15.

  • Lemma 18 bounds the weighted intersection count for each fixed matching, while concentration of |B ∩ Fs+1| makes its average contribution negative and completes Lemma 15.The small-α case uses Proposition 13; the other case uses Theorem 12.Source: §4.1 · p. 11, §4.2 · p. 13

5. Proof of Theorem 2

Theorem 2 extends bounds on the Erdős Matching Conjecture across the full parameter range. Its proof extrapolates from one matching ratio using a Kneser-graph inequality.

5. Proof of Theorem 2

  • Theorem 2 follows from Theorem 1 together with a proposition that allows any bounds on the EMC to be extended to the full range.Source: §5 · p. 13
  • An upper bound at matching ratio x extends to y in [x, 1/k] by combining it with the trivial bound at 1/k.The resulting upper bound is a convex combination of the assumed bound at x and the trivial endpoint bound.Source: §5 · p. 13
  • The proof uses induction on yn and a Kneser-graph inequality to select a set A and bound the subfamily disjoint from A.For a random A, the expected size of the subfamily disjoint from A is controlled using the inequality for the Kneser graph.Source: §5 · pp. 13–14

6. Applications of Theorem 1 and related questions

The section develops applications and related questions arising from Theorem 1, including relaxations of the EMC, Dirac thresholds, other combinatorial problems, and deviation bounds for sums of random variables.

6. Applications of Theorem 1 and related questions

  • The section frames these results as applications of Theorem 1, including consequences for Dirac thresholds and deviations of sums of random variables.It also identifies relaxations of the EMC and other combinatorial applications as topics covered in the section.Source: §6 · p. 14

6.1. Relaxations of the Erd˝os Matching Conjecture.

  • The section surveys fractional and asymptotic relaxations of the EMC, defining fractional matching through vertex-constrained edge weights and noting that nonintegral s is more complicated.The fractional matching number is the maximum total weight with incident weight at each vertex at most 1; the section also discusses fixed k with matching number linear in n.Source: §6.1 · pp. 14–15

6.2. Dirac thresholds.

  • For Dirac thresholds, the paper gives exact values of m*_d(n, k) in new cases and states that (44) holds for d ≥ 3k/8.The new cases include sufficiently large n with 5d ≥ 2k−2; the authors also give a simpler proof of Theorem 22 and note its implication that the fractional and integral asymptotic EMC forms are equivalent for x < 1/k.Source: §6.2 · p. 16

6.3. Other combinatorial applications.

  • EMC results support other combinatorial applications, while the paper notes that its proof does not extend to cross-dependent families and reports a resolution of the rainbow EMC for n > 300sk.The section also reports the use of fractional EMC results for the Manickam–Miklós–Singhi conjecture when n ≥ 33k².Source: §6.3 · p. 17

6.4. Deviations of sums of nonnegative variables.

  • For k = 4 and x ≤ 1/5, Corollary 27 establishes equalities (38) and (39) for deviations of sums of nonnegative variables.The authors state that an optimized corollary of Theorem 1 would imply those equalities, as well as (4) and (37), for x ≤ 0.18.Source: §6.4 · p. 18

7. Proof of Theorem 22

The proof of Theorem 22 reduces threshold questions to finding large matchings in an auxiliary hypergraph. A low-codegree matching theorem supplies that step, while the argument establishes continuity of the fractional threshold function.

7. Proof of Theorem 22

  • The proof follows the steps of Theorem 21, using randomly selected sets and fractional matchings to construct a hypergraph with high probability having controlled codegrees and sufficient average degree.The construction uses sets R_i with bounded overlaps, then selects edges according to fractional matching weights; concentration bounds establish the listed properties.Source: §7 · p. 19
  • For an n-vertex k-uniform hypergraph with d(H)/∆(H) = c and sufficiently small codegrees, Theorem 29 guarantees a matching covering at least a c−δ proportion of vertices.The theorem requires n sufficiently large and bounds every pair's codegree by ε∆(H).Source: §7 · p. 19

7.1. Proof of Theorem 29.

  • The authors adapt the approach from [42, Theorem 2.13] and apply the Pippenger–Spencer partition theorem to obtain the matching guarantee in Theorem 29.The constructed hypergraph is partitioned into matchings, and one matching is chosen whose intersection with H is at least the expected size.Source: §7 · p. 19, §7.1 · p. 20

7. Proof of Theorem 22

  • The proof concludes that c_x = c*_x for x in (0, 1/k), using continuity of c*_x, which the authors establish.The function c*_x is monotone and continuous on [0, 1/k).Source: §7 · p. 19
  • The proof notes a boundary difference at x = 1/k: c*_x can be treated there, whereas c_x is discontinuous because of parity-based constructions.The continuity result for c*_x is stated on [0, 1/k).Source: §7 · pp. 19–20

8. Concluding remarks

The concluding remarks report improved bounds for small k while identifying the full range of the Erdős Matching Conjecture as unresolved. They also pose a diversity extremal problem and note further applications of the paper’s concentration method.

8. Concluding remarks

  • For k=4–9, the appendix yields bounds proving the EMC for s≥s0 and n≥c_k(k−1)s+s, with c4=1.58, c5=1.6, c6,c7=1.61, and c8,c9=1.62.The paper says its bounds can be further optimized for k<10.Source: §8 · pp. 20–21
  • Proving the EMC for every n>(s+1)k remains open in the authors’ account and, they say, requires new ideas.Source: §8 · p. 21
  • The authors pose the problem of maximizing s-diversity among shifted families, which could improve bounds on β and yield a universal bound on m(n,k,s).For initial families, the minimum in their definition is attained at T=[s].Source: §8 · p. 21
  • The paper notes that its concentration method has also been applied to rainbow EMC results and to density changes under restriction to a random fixed-size subset.The latter application advanced a question about distinct intersections in intersecting families.Source: §8 · p. 21

10. Appendix. How to get good bounds on β or α in Lemma 16

The appendix develops estimates for Lemma 16 and verifies the conditions used in Lemma 17, including for large k. Its improved bound contributes to the sharper estimates reported for small k.

10.1. Bounds on |Gi|. 

  • The bounds in subsection 10.1 are used to show that |G_i| decreases exponentially as i increases.The appendix also notes that the numerical bounds are not optimal within its approach, balancing tighter main-theorem bounds against lengthy estimates.Source: §10.1 · p. 23, §10 · p. 23

10.2. Proof of Lemma 17.

  • The bound c(k−1)−τ, with τ(k) tending to 1/2 as k grows, helps obtain improved bounds such as those in Theorem 32.Source: §10.2 · p. 24
  • For 4≤k≤10, the chosen ρ values give 0.007-consistency and 0.08-robustness; for 10<k≤2·10^4, they give 0.028-consistency and 0.004-robustness.Source: §10.2 · pp. 25–26
  • From 0.005-robustness at k = 2·10^4 with ρ_i as in B, (56) is 0.0005-robust for the same ρ_i at any k′ > 2·10^4; (54) and (55) are 0.0008-consistent there.Source: §10.2 · p. 27
Loading 1806.08855v3…