DOI: 10.1016/j.disc.2025.114654">
 

Maximal intersecting families revisited

Document Type

Article

Publication Date

2026

Department/School

Mathematics

Publication Title

Discrete Mathematics

Abstract

The well-known Erdős–Ko–Rado theorem states that for n>2k, every intersecting family of k-sets of [n]:={1,…,n} has at most (n−1k−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. Further stability results were studied by Han and Kohayakawa (2017) and Huang and Peng (2024). Two families F and G are called cross-intersecting if for every F∈F and G∈G, the intersection F∩G is non-empty. Let k≥1,t≥0 and n≥2k+t be integers. Frankl (2016) proved that if F⊆([n]k+t) and G⊆([n]k) are cross-intersecting families, and F is non-empty and (t+1)-intersecting, then |F|+|G|≤(nk)−(n−k−tk)+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ő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.

Comments

J. Liu is a faculty member in EMU's Department of Mathematics and Statistics.

Link to Published Version

DOI: 10.1016/j.disc.2025.114654

Link to Full Text

EMU Library Accessibility Request

Share

COinS