Geodesic
Structure and supersaturation for intersecting families
József Balogh1 ; Shagnik Das2 ; Hong Liu3 ; Maryam Sharifzadeh3 ; Tuan Tran4
1University of Illinois at Urbana-Champaign and Moscow Institute of Physics and Technology
2Freie Universität Berlin
3University of Warwick
4ETH Zürich
The electronic journal of combinatorics, Tome 26 (2019) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 \ge 2sk + 38s^4$, and show that almost all $k$-uniform intersecting families on vertex set $[n]$ are trivial when $n\ge (2+o(1))k$.
DOI : 10.37236/7683
Classification : 05D05, 05C30, 05C65
Mots-clés : removal lemma for disjoint pairs

József Balogh  1   ; Shagnik Das  2   ; Hong Liu  3   ; Maryam Sharifzadeh  3   ; Tuan Tran  4

1 University of Illinois at Urbana-Champaign and Moscow Institute of Physics and Technology
2 Freie Universität Berlin
3 University of Warwick
4 ETH Zürich 
@article{10_37236_7683,
     author = {J\'ozsef Balogh and Shagnik Das and Hong Liu and Maryam Sharifzadeh and Tuan Tran},
     title = {Structure and supersaturation for intersecting families},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {2},
     doi = {10.37236/7683},
     zbl = {1414.05286},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7683/}
}
TY  - JOUR
AU  - József Balogh
AU  - Shagnik Das
AU  - Hong Liu
AU  - Maryam Sharifzadeh
AU  - Tuan Tran
TI  - Structure and supersaturation for intersecting families
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7683/
DO  - 10.37236/7683
ID  - 10_37236_7683
ER  - 
%0 Journal Article
%A József Balogh
%A Shagnik Das
%A Hong Liu
%A Maryam Sharifzadeh
%A Tuan Tran
%T Structure and supersaturation for intersecting families
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7683/
%R 10.37236/7683
%F 10_37236_7683
József Balogh; Shagnik Das; Hong Liu; Maryam Sharifzadeh; Tuan Tran. Structure and supersaturation for intersecting families. The electronic journal of combinatorics, Tome 26 (2019) no. 2. doi: 10.37236/7683

Cité par Sources :