Structure and supersaturation for intersecting families
OPEN ACCESS
Author / Producer
Date
2019-05-31
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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
Publication status
published
External links
Editor
Book title
Journal / series
Volume
26 (2)
Pages / Article No.
Publisher
Electronic Journal of Combinatorics
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin