Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 

 

The structure of large intersecting families


Authors: Alexandr Kostochka and Dhruv Mubayi
Journal: Proc. Amer. Math. Soc. 145 (2017), 2311-2321
MSC (2010): Primary 05B07, 05C65, 05C70, 05D05, 05D15
DOI: https://doi.org/10.1090/proc/13390
Published electronically: December 9, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A collection of sets is intersecting if every two members have nonempty intersection. We describe the structure of intersecting families of $ r$-sets of an $ n$-set whose size is quite a bit smaller than the maximum $ {n-1 \choose r-1}$ given by the Erdős-Ko-Rado Theorem. In particular, this extends the Hilton-Milner theorem on nontrivial intersecting families and answers a recent question of Han and Kohayakawa for large $ n$. In the case $ r=3$ we describe the structure of all intersecting families with more than 10 edges. We also prove a stability result for the Erdős matching problem. Our short proofs are simple applications of the Delta-system method introduced and extensively used by Frankl since 1977.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05B07, 05C65, 05C70, 05D05, 05D15

Retrieve articles in all journals with MSC (2010): 05B07, 05C65, 05C70, 05D05, 05D15


Additional Information

Alexandr Kostochka
Affiliation: University of Illinois at Urbana–Champaign, Urbana, Illinois 61801 — and — Sobolev Institute of Mathematics, Novosibirsk 630090, Russia
Email: kostochk@math.uiuc.edu

Dhruv Mubayi
Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607
Email: mubayi@uic.edu

DOI: https://doi.org/10.1090/proc/13390
Received by editor(s): February 3, 2016
Received by editor(s) in revised form: February 4, 2016, and July 20, 2016
Published electronically: December 9, 2016
Additional Notes: The research of the first author was supported in part by NSF grants DMS-1266016 and DMS-1600592 and by grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research
The research of the second author was partially supported by NSF grant DMS-1300138
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2016 American Mathematical Society