Date and Time: 12/04/2025, 16:30--17:30

Location: 25 Park Place, Room 1441

Colloquium: Maximal independent sets in the middle two layers of the Boolean lattice

Speaker: József Balogh, University of Illinois at Urbana–Champaign

Speaker's website: https://sites.google.com/view/jozsefbaloghmath/home

Title: Maximal independent sets in the middle two layers of the Boolean lattice

Abstract: In the lecture, problems related to independent sets in hypercube will be discussed, with focus on the following recent result:
Let B(2d−1,d) be the subgraph of the hypercube 2d−1 induced by its two largest layers. Duffus, Frankl and Rödl proposed the problem of finding the asymptotics for the logarithm of the number of maximal independent sets in B(2d−1,d). Ilinca and Kahn determined the logarithmic asymptotics and reiterated the question of what their order of magnitude is. We determine the number of maximal independent sets in B(2d−1,d) and describe their typical structure. The proof uses a new variation of Sapozhenko's Graph Container Lemma, a new isoperimetric lemma, a theorem of Hujter and Tuza on the number of maximal independent sets in triangle-free graphs and a stability version of their result by Kahn and Park, among other tools.
Joint work with Ce Chen and Ramon Garcia.

Speaker's biography: József Balogh received his Ph.D. from the University of Memphis in 2001 under the supervision of Béla Bollobás. After being a postdoc at AT&T, IAS, and Ohio State, he jointed the University of Illinois at Urbana–Champaign in 2005. His research areas lie in extremal and probabilistic combinatorics and their applications. He has published about 200 research papers and graduated 18 Ph.D. students. He received Polya Prize in combinatorics in 2016 and Steele Prize in 2024 for seminal contributions to research. He is an invited speaker of the International Congress of Mathematicians in 2018, an AMS Fellow and Simons Fellow, and foreign member of the Hungarian Academy of Sciences

Host: Yi Zhao (yzhao6@gsu.edu)