Structure and Supersaturation for Intersecting Families

0494719 - ÚI 2020 US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GJ16-07822Y; GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985807
Klíčová slova: Erdos-Ko-Rado theorem * intersecting families * removal lemma * supersaturation * counting
Obor OECD: Pure mathematics
Impakt faktor: 0.641, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0287810