Department of Mathematics Calendar

Back to Listing

The Department of Mathematics Calendar has moved to Webtools. Anyone may submit an event by clicking the "+" button (upper right). All events will be reviewed before acceptance. Please email Peggy Currid if you have any questions about submitting an event.

 

Note: you may search past and future events by clicking on the magnifying glass icon on the main Calendar page.

 

For an archive of past events: https://math.illinois.edu/research/seminars-department-calendar

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
E-Mail
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.

link for robots only