Maximal intersecting families revisited
Discrete Mathematics · 2026-01 · 349 (1) · 114654
DOI: 10.1016/j.disc.2025.114654 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics, 2026-01. Verfasst von Yongjiang Wu und 4 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 45 Literaturangaben. Gefördert von: Natural Science Foundation of Guizhou Province, National Natural Science Foundation of China.
Abstract (Originalsprache)
The well-known Erd\H{o}s--Ko--Rado theorem states that for $n>2k$, every intersecting family of $k$-sets of $[n]:=\{1,\ldots ,n\}$ has at most $ {n-1 \choose k-1}$ sets, and the extremal family consists of all $k$-sets containing a fixed element (called a full star). The Hilton--Milner theorem provides a stability result by determining the maximum size of a uniform intersecting family that is not a subfamily of a full star. The further stabilities were studied by Han and Kohayakawa (2017) and Huang and Peng (2024). Two families $\mathcal{F}$ and $\mathcal{G}$ are called cross-intersecting if for every $F\in \mathcal{F}$ and $G\in \mathcal{G}$, the intersection $F\cap G$ is non-empty. Let $k \geq 1, t\ge 0$ and $n \geq 2 k+t$ be integers. Frankl (2016) proved that if $\mathcal{F} \subseteq\binom{[n]}{k+t}$ and $\mathcal{G} \subseteq\binom{[n]}{k}$ are cross-intersecting families, and $\mathcal{F}$ is non-empty and $(t+1)$-intersecting, then $|\mathcal{F}|+|\mathcal{G}| \leq\binom{n}{k}-\binom{n-k-t}{k}+1$. Recently, Wu (2023) sharpened Frankl's result by establishing a stability variant. The aim of this paper is two-fold. Inspired by the above results, we first prove a further stability variant that generalizes both Frankl's result and Wu's result. Secondly, as an interesting application, we illustrate that the aforementioned results on cross-intersecting families could be used to establish the stability results of the Erd\H{o}s--Ko--Rado theorem. More precisely, we present new short proofs of the Hilton--Milner theorem, the Han--Kohayakawa theorem and the Huang--Peng theorem. Our arguments are more straightforward, and it may be of independent interest.
Förderung
- Natural Science Foundation of Guizhou Province
- National Natural Science Foundation of China
Zitieren
APA
Wu, Y., Li, Y., Feng, L., Liu, J., & Yu, G. (2026). Maximal intersecting families revisited. Discrete Mathematics, 349(1), 114654. https://doi.org/10.1016/j.disc.2025.114654
Vancouver
Wu Y, Li Y, Feng L, Liu J, Yu G. Maximal intersecting families revisited. Discrete Mathematics. 2026;349(1):114654. doi:10.1016/j.disc.2025.114654
BibTeX
@article{Wu2026,
author = {Wu, Yongjiang and Li, Yongtao and Feng, Lihua and Liu, Jiuqiang and Yu, Guihai},
title = {Maximal intersecting families revisited},
journal = {Discrete Mathematics},
year = {2026},
volume = {349},
number = {1},
pages = {114654},
doi = {10.1016/j.disc.2025.114654}
}
EUVIMED