Non-trivial d-wise intersecting families

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:178

Article

O'Neill, Jason¹  Verstraete, Jacques¹ 

[1] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA

关键词: Extremal set theory;    Delta system method;    Intersecting families;   

DOI  :  10.1016/j.jcta.2020.105369

来源: Elsevier

【 摘 要 】

For an integer d >= 2, a family F of sets is d-wise intersecting if for any distinct sets A(1), A(2), ..., A(d) is an element of F, A(1) boolean AND A(2)boolean AND ...boolean AND A(d) not equal emptyset, and non-trivial if boolean AND(A is an element of F) A = emptyset. Hilton and Milner conjectured that for k >= d >= 2 and large enough n, the extremal (i.e. largest) non-trivial d-wise intersecting family of k-element subsets of [n] is, up to isomorphism, one of the following two families: A(k, d) = {A is an element of (([n])(k)) : vertical bar A boolean AND [d + 1]vertical bar >= d} H(k, d) = {A is an element of (([n])(k)) : [d - 1] subset of A, A boolean AND[d, k + 1] not equal emptyset} boolean OR {[k + 1] \{i} : i is an element of [d - 1]}. The celebrated Hilton-Milner Theorem states that H(k, 2) is the unique, up to isomorphism, extremal non-trivial intersecting family for k > 3. We prove the conjecture and prove a stability theorem, stating that any large enough nontrivial d-wise intersecting family of k-element subsets of [n] is a subfamily of A(k,d) or H(k, d). (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free