Non-trivially intersecting multi-part families

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:156

Article

Kwan, Matthew¹  Sudakov, Benny¹  Vieira, Pedro¹ 

[1] ETH, Dept Math, CH-8092 Zurich, Switzerland

关键词: Extremal set theory;    Intersecting families;    Erdos-Ko-Rado theorem;    Hilton-Milner theorem;   

DOI  :  10.1016/j.jcta.2017.12.001

来源: Elsevier

【 摘 要 】

We say a family of sets is intersecting if any two of its sets intersect, and we say it is trivially intersecting if there is an element which appears in every set of the family. In this paper we study the maximum size of a non-trivially intersecting family in a natural multi-part setting. Here the ground set is divided into parts, and one considers families of sets whose intersection with each part is of a prescribed size. Our work is motivated by classical results in the single-part setting due to Erdos, Ko and Rado, and Hilton and Milner, and by a theorem of Frankl concerning intersecting families in this multi-part setting. In the case where the part sizes are sufficiently large we determine the maximum size of a non-trivially intersecting multi-part family, disprovirig a conjecture of Alon and Katona. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free