Department of

July 2021 August 2021 September 2021 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 1 2 3 4 5 6 7 1 2 3 4 4 5 6 7 8 9 10 8 9 10 11 12 13 14 5 6 7 8 9 10 11 11 12 13 14 15 16 17 15 16 17 18 19 20 21 12 13 14 15 16 17 18 18 19 20 21 22 23 24 22 23 24 25 26 27 28 19 20 21 22 23 24 25 25 26 27 28 29 30 31 29 30 31 26 27 28 29 30

Tuesday, August 31, 2021

**Abstract:** An independent set $I$ of a graph $G$ is said to be a maximal independent set (MIS) if it is maximal with respect to set inclusion. Nielsen proved that the maximum number of MIS's of size $k$ in an $n$-vertex graph is asymptotic to $(n/k)^k$, with the extremal construction being a disjoint union of $k$ cliques with sizes as close to $n/k$ as possible. In this talk we study how many MIS's of size $k$ an $n$-vertex graph $G$ can have if $G$ does not contain a clique $K_t$. We prove for all fixed $k$ and $t$ that there exist such graphs with $n^{\lfloor\frac{(t-2)k}{t-1}\rfloor-o(1)}$ MIS's of size $k$ by utilizing recent work of Gowers and B. Janzer on a generalization of the Ruzsa-Szemeredi problem. We prove that this bound is essentially best possible for triangle-free graphs when $k\le 4$. This is joint work with Xiaoyu He and Jiaxi Nie.

For Zoom information, please contact Sean at SEnglish (at) illinois (dot) edu.