## Graph Theory and Combinatorics Seminar: Independence number of random subgraphs of the hypercube

- Event Type
- Seminar/Symposium
- Sponsor
- N/A
- Location
- 345 AH
- Date
- Nov 16, 2021 1:00 pm
- Speaker
- Robert Krueger (UIUC)
- Contact
- Sean English
- senglish@illinois.edu
- Views
- 10
The discrete hypercube of dimension d is a d-regular bipartite graph on 2^d vertices whose maximum size independent set has size 2^(d-1). In this talk, we will prove that if we keep each edge with constant probability p > 1/2, the independence number is still 2^(d-1) with probability tending to 1 as d tends to infinity. In fact, much more about the independence number of this random subgraph of the cube is known for general p. We will also discuss the same theorem but for the random induced subgraph of the cube, where we include each vertex with probability p. These proofs are simplifications of earlier graph container-like arguments concerning random versions of the Erdos-Ko-Rado theorem, which will be discussed if time permits. This is joint work with Jozsef Balogh.