dorsal/arxiv
View SchemaNearly Erd\H{o}s-Ko-Rado theorems
| Authors | Gyula O. H. Katona, Jian Wang |
|---|---|
| Categories | |
| ArXiv ID | 2601.06871vv1 |
| URL | https://arxiv.org/abs/2601.06871 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
If a family $\mathcal{F}$ of $k$-element subsets of an $n$-element set is pairwise intersecting, $2k\leq n$ then $|\mathcal{F}|\leq {n-1\choose k-1}$ holds by the celebrated Erd\H{o}s-Ko-Rado theorem. But an intersecting family obviously satisfies the condition $${\ell \choose 2}\leq \sum_{1\leq i<j\leq \ell}|F_i\cap F_j| $$ for any $\ell$ distinct members of the family. It has been proved in [5] that even if ${\ell \choose 2}$ is replaced by ${\ell -1 \choose 2}+1$ the conclusion $|\mathcal{F}|\leq {n-1\choose k-1}$ remains valid for large $n$. However the 1 cannot be omitted, because there is a larger family satisfying that weaker condition. In the present paper we determine the largest size of the family under this weaker condition when $n$ is sufficiently large. All of these are treated in the more general setting of $t$-intersecting families.
{
"annotation_id": "852b4a0f-382d-4f3e-8e0c-67f6b2108302",
"date_created": "2026-02-17T05:53:08.663000Z",
"date_modified": "2026-02-17T05:53:08.663000Z",
"file_hash": "4e3a9101e92670dc01722484020fd9d5d5fc9f0fe76433219def870adf733c25",
"private": false,
"record": {
"abstract": "If a family $\\mathcal{F}$ of $k$-element subsets of an $n$-element set is pairwise intersecting, $2k\\leq n$ then $|\\mathcal{F}|\\leq {n-1\\choose k-1}$ holds by the celebrated Erd\\H{o}s-Ko-Rado theorem. But an intersecting family obviously satisfies the condition $${\\ell \\choose 2}\\leq \\sum_{1\\leq i\u003cj\\leq \\ell}|F_i\\cap F_j| $$ for any $\\ell$ distinct members of the family. It has been proved in [5] that even if ${\\ell \\choose 2}$ is replaced by ${\\ell -1 \\choose 2}+1$ the conclusion $|\\mathcal{F}|\\leq {n-1\\choose k-1}$ remains valid for large $n$. However the 1 cannot be omitted, because there is a larger family satisfying that weaker condition. In the present paper we determine the largest size of the family under this weaker condition when $n$ is sufficiently large. All of these are treated in the more general setting of $t$-intersecting families.",
"arxiv_id": "2601.06871",
"authors": [
"Gyula O. H. Katona",
"Jian Wang"
],
"categories": [
"math.CO"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Nearly Erd\\H{o}s-Ko-Rado theorems",
"url": "https://arxiv.org/abs/2601.06871",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ffb5247b-3057-43fb-bc66-711a3983233f",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}