Extremal Families for the Erdős--Kleitman Problem: The Missing Constructions
Abstract
For integers n≥ s≥2, let e(n,s) be the maximum size of a family ℱ⊆2[n] with no s pairwise disjoint members. The problem of determining e(n,s), now called the Erdős--Kleitman problem, is closely related to the well-known Erdős matching problem. Frankl and Kupavskii posed a meta-conjecture predicting that the maximum is always attained by a weighted family. Fix m≥3, write n=ms+c with 0≤ c<s, and set ℓ=s−c. For 0≤ k≤ m, let ak=ms−kc−1. For A∈binom[n]ak, define ℋk(m,s,ℓ;A):= {F⊆[n]: k|F|+|F∩ A|≥ m(k+1)}. This defines a unified class of weighted families with matching number less than s. Among these families, ℋ0, ℋ1, and ℋm were previously known to be extremal in different ranges of c. We show that for 1≤ k≤ m−1, all families ℋk are uniquely extremal in some ranges of c. More precisely, we prove that for every m≥3 and every 1≤ k≤ m−1, there exist constants α=α(m,k)>0, β=β(m,k)>0 and an integer s0=s0(m,k) such that, for all integers s≥ s0 and all integers c with 0≤ c<s, the only extremal families for e(n,s) are the families ℋk(m,s,ℓ;A) with A∈binom[n]ak whenever βs(k−1)/k≤ c≤ αsk/(k+1). In particular, this result determines an infinite number of new extremal families for the Erdős--Kleitman problem and verifies the Frankl--Kupavskii meta-conjecture in these ranges. This also provides a quantitative extension of the result of Kupavskii and Sokolov on the extremality of ℋ1.
Related
- Uniform asymptotics for the Kleitman-West problem
- NeuralCert: certified computational discovery of extremal mathematical constructions
- Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions
- Sunflower-Free Uniform Families: Recursive Constructions and Explicit Bounds
- Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study
BibTeX
@misc{chi2026extremal,
title = {{Extremal Families for the Erdős--Kleitman Problem: The Missing Constructions}},
author = {Cheng Chi and Yan Wang},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2607.25611},
eprint = {2607.25611},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.25611},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Extremal Families for the Erdős--Kleitman Problem: The Missing Constructions
AU - Cheng Chi
AU - Yan Wang
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2607.25611
UR - https://arxiv.org/abs/2607.25611
AB - For integers n≥ s≥2, let e(n,s) be the maximum size of a family ℱ⊆2^[n] with no s pairwise disjoint members. The problem of determining e(n,s), now called the Erdős--Kleitman problem, is closely related to the well-known Erdős matching problem. Frankl and Kupavskii posed a meta-conjecture predicting that the maximum is always attained by a weighted family. Fix m≥3, write n=ms+c with 0≤ c<s, and set ℓ=s−c. For 0≤ k≤ m, let a_k=ms−kc−1. For A∈binom[n]a_k, define ℋ^k(m,s,ℓ;A):= {F⊆[n]: k|F|+|F∩ A|≥ m(k+1)}. This defines a unified class of weighted families with matching number less than s. Among these families, ℋ^0, ℋ^1, and ℋ^m were previously known to be extremal in different ranges of c. We show that for 1≤ k≤ m−1, all families ℋ^k are uniquely extremal in some ranges of c. More precisely, we prove that for every m≥3 and every 1≤ k≤ m−1, there exist constants α=α(m,k)>0, β=β(m,k)>0 and an integer s_0=s_0(m,k) such that, for all integers s≥ s_0 and all integers c with 0≤ c<s, the only extremal families for e(n,s) are the families ℋ^k(m,s,ℓ;A) with A∈binom[n]a_k whenever βs^(k−1)/k≤ c≤ αs^k/(k+1). In particular, this result determines an infinite number of new extremal families for the Erdős--Kleitman problem and verifies the Frankl--Kupavskii meta-conjecture in these ranges. This also provides a quantitative extension of the result of Kupavskii and Sokolov on the extremality of ℋ^1.
ER -