The largest K_r-free set of vertices in a random graph

In the random graph G(n,1/2), classic works show that with high probability the independence number is concentrated on at most two values; this phenomenon is referred to as two-point concentration. We consider a generalization of this question: for a fixed r, let alpha_r be the size of the largest K_r-free subgraph of G(n,1/2). In the case of r = 2, we see that alpha_r is the independence number. We precisely describe the concentration of alpha_r for each r. Perhaps surprisingly, two-point concentration holds for r = 2 and r= 3 and fails for all other r. In general, alpha_r lies in an interval of constant length that varies in a non-monotonic fashion from 1 to floor(r/2) + 1. I will describe this result and outline various open problems surrounding this question. This is based on joint work with Tom Bohman and Dhruv Mubayi.

For information about the Richard P. Stanley Seminar in Combinatorics, visit… https://math.mit.edu/combin/