EUVIMEDEUVIMED entdecken
Crossref

Maximal intersecting families revisited

Yongjiang Wu, Yongtao Li, Lihua Feng, Jiuqiang Liu, Guihai Yu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →