Structure and Supersaturation for Intersecting Families

0494719 - ÚI 2020 US eng J - Journal Article
Balogh, J. - Das, S. - Liu, H. - Sharifzadeh, M. - Tran, Tuan
Structure and Supersaturation for Intersecting Families.
Electronic Journal of Combinatorics. Roč. 26, č. 2 (2019), č. článku P2.34. ISSN 1077-8926. E-ISSN 1077-8926
R&D Projects: GA ČR GJ16-07822Y; GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : Erdos-Ko-Rado theorem * intersecting families * removal lemma * supersaturation * counting
OECD category: Pure mathematics
Impact factor: 0.641, year: 2019
https://arxiv.org/abs/1802.08018

The extremal problems regarding the maximum possible size of intersecting families of various combinatorial objects have been extensively studied. In this paper, we investigate supersaturation extensions, which in this context ask for the minimum number of disjoint pairs that must appear in families larger than the extremal threshold. We study the minimum number of disjoint pairs in families of permutations and in k-uniform set families, and determine the structure of the optimal families. Our main tool is a removal lemma for disjoint pairs. We also determine the typical structure of k-uniform set families without matchings of size s when n≥2sk+38s4, and show that almost all k-uniform intersecting families on vertex set [n] are trivial when n≥(2+o(1))k.
Permanent Link: http://hdl.handle.net/11104/0287810