Most Probably Intersecting Hypergraphs

Abstract

The celebrated Erdős-Ko-Rado theorem shows that for n≥2k the largest intersecting k-uniform set family on [n] has size (n−1k−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.