Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics Seminar

Sam Spiro

UCSD

Maximal Independent Sets in Clique-free Graphs

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-Szemer\'edi problem. We prove that this bound is essentially best possible for triangle-free graphs when $k\le 4$. \medskip This is joint work with Xiaoyu He and Jiaxi Nie.

Host: Jacques Verstraete

October 5, 2021

4:00 PM

APM 6402 (Halkin Room)

****************************