Algebraic Graph Theory - József Balogh

Title: On Robustness of The Erdős--Ko--Rado Theorem 

Abstract: A family of subsets of $[n]$ is \emph{intersecting} if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics, starting with the well-known Erdős-Ko-Rado Theorem. We consider two extensions of it:

Counting variant: Frankl--Kupavskii and Balogh--Das--Liu--Sharifzadeh--Tran showed that for $n\geq 2k + c\sqrt{k\ln k}$, almost all $k$-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for $n\geq 2k+ 100\ln k$.

Random variant: For positive integers $n$ and $k$ with $n\geq 2k+1$, the Kneser graph $K(n,k)$ is the graph with vertex set consisting of all $k$-sets of $\{1,\dots,n\}$, where two $k$-sets are adjacent exactly when they are disjoint. Let $K_p(n,k)$ be a random spanning subgraph of $K(n,k)$ where each edge is included independently with probability $p$. Bollob\'as, Narayanan, and Raigorodskii asked for what $p$ does $K_p(n,k)$ have the same independence number as $K(n,k)$ with high probability. Building on work of Das and Tran and of Devlin and Kahn, we resolve this question.

Our proofs uses, among others, the graph container method and the Das--Tran removal lemma.

It is joint work with Lina Li, Ramon Garcia, Adam Wagner; and with Robert Krueger and Haoran Luo.