Balogh József: On Robustness of The Erdős--Ko--Rado Theorem.

Description of video

Date: 5/13/21
Speaker :Balogh József


    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 Erdos-Ko-Rado Theorem.
    We consider two extensions of it:

    Counting variant: Frankl--Kupavskii and Balogh--Das--Liu--Sharifzadeh--Tran showed that for n2k+cklnk, almost all k-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for n2k+100lnk.

    Random variant: For positive integers n and k with n2k+1, the Kneser graph K(n,k) is the graph with vertex set consisting of all k-sets of {1,,n}, where two k-sets are adjacent exactly when they are disjoint. Let Kp(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 Kp(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.