Erdős Matching (Conjecture) Theorem
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910278277398528 |
|---|---|
| author | Mishra, Tapas Kumar |
| author_facet | Mishra, Tapas Kumar |
| contents | Let $\mathcal{F}$ be a family of $k$-sized subsets of $[n]$ that does not contain $s$ pairwise disjoint subsets.
The Erdős Matching Conjecture, a celebrated and long-standing open problem in extremal combinatorics, asserts the maximum cardinality of $\mathcal{F}$ is upper bounded by
$\max\left\{\binom{sk-1}{k}, \binom{n}{k}-\allowbreak \binom{n-s+1}{k}\right\}$.
These two bounds correspond to the sizes of two canonical extremal families: one in which all subsets are contained within a ground set of $sk-1$ elements, and one in which every subset intersects a fixed set of $s-1$ elements.
In this paper, we prove the conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_01471 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Erdős Matching (Conjecture) Theorem Mishra, Tapas Kumar Combinatorics Discrete Mathematics 05DXX G.2.1 Let $\mathcal{F}$ be a family of $k$-sized subsets of $[n]$ that does not contain $s$ pairwise disjoint subsets. The Erdős Matching Conjecture, a celebrated and long-standing open problem in extremal combinatorics, asserts the maximum cardinality of $\mathcal{F}$ is upper bounded by $\max\left\{\binom{sk-1}{k}, \binom{n}{k}-\allowbreak \binom{n-s+1}{k}\right\}$. These two bounds correspond to the sizes of two canonical extremal families: one in which all subsets are contained within a ground set of $sk-1$ elements, and one in which every subset intersects a fixed set of $s-1$ elements. In this paper, we prove the conjecture. |
| title | Erdős Matching (Conjecture) Theorem |
| topic | Combinatorics Discrete Mathematics 05DXX G.2.1 |
| url | https://arxiv.org/abs/2602.01471 |