The celebrated Erdős-Ko-Rado theorem shows that for $n \ge 2k$ the largest intersecting $k$-uniform set family on $[n]$ has size $\binom{n-1}{k-1}$. It is natural to ask how far from intersecting larger set families must be. Katona, Katona and Katona introduced the notion of most probably intersecting families, which maximise the probability of random subfamilies being intersecting.We consider the most probably intersecting problem for $k$-uniform set families. We provide a rough structural characterisation of the most probably intersecting families and, for families of particular sizes, show that the initial segment of the lexicographic order is optimal.
@article{10_37236_4784,
author = {Shagnik Das and Benny Sudakov},
title = {Most probably intersecting hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/4784},
zbl = {1310.05150},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4784/}
}
TY - JOUR
AU - Shagnik Das
AU - Benny Sudakov
TI - Most probably intersecting hypergraphs
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/4784/
DO - 10.37236/4784
ID - 10_37236_4784
ER -
%0 Journal Article
%A Shagnik Das
%A Benny Sudakov
%T Most probably intersecting hypergraphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4784/
%R 10.37236/4784
%F 10_37236_4784
Shagnik Das; Benny Sudakov. Most probably intersecting hypergraphs. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4784
