Non-trivially intersecting multi-part families
Kwan MA, Sudakov B, Vieira P. 2018. Non-trivially intersecting multi-part families. Journal of Combinatorial Theory Series A. 156, 44–60.
Download (ext.)
https://arxiv.org/abs/1703.09946
[Preprint]
Journal Article
| Published
| English
Scopus indexed
Author
Kwan, Matthew AlanISTA ;
Sudakov, Benny;
Vieira, Pedro
Abstract
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 Erdős, 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, disproving a conjecture of Alon and Katona.
Publishing Year
Date Published
2018-05-01
Journal Title
Journal of Combinatorial Theory Series A
Publisher
Elsevier
Volume
156
Page
44-60
ISSN
IST-REx-ID
Cite this
Kwan MA, Sudakov B, Vieira P. Non-trivially intersecting multi-part families. Journal of Combinatorial Theory Series A. 2018;156:44-60. doi:10.1016/j.jcta.2017.12.001
Kwan, M. A., Sudakov, B., & Vieira, P. (2018). Non-trivially intersecting multi-part families. Journal of Combinatorial Theory Series A. Elsevier. https://doi.org/10.1016/j.jcta.2017.12.001
Kwan, Matthew Alan, Benny Sudakov, and Pedro Vieira. “Non-Trivially Intersecting Multi-Part Families.” Journal of Combinatorial Theory Series A. Elsevier, 2018. https://doi.org/10.1016/j.jcta.2017.12.001.
M. A. Kwan, B. Sudakov, and P. Vieira, “Non-trivially intersecting multi-part families,” Journal of Combinatorial Theory Series A, vol. 156. Elsevier, pp. 44–60, 2018.
Kwan MA, Sudakov B, Vieira P. 2018. Non-trivially intersecting multi-part families. Journal of Combinatorial Theory Series A. 156, 44–60.
Kwan, Matthew Alan, et al. “Non-Trivially Intersecting Multi-Part Families.” Journal of Combinatorial Theory Series A, vol. 156, Elsevier, 2018, pp. 44–60, doi:10.1016/j.jcta.2017.12.001.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1703.09946