14:00
Small maximal independent sets in regular graphs
Abstract
We study the minimum size of a maximal independent set in a regular graph, that is, the smallest sets which are both independent and dominating. In a balanced complete bipartite graph, every maximal independent set contains exactly half of the vertices, so large degree alone does not guarantee a small maximal independent set.
In this talk I will show that regular graphs with bounded codegrees admit much smaller maximal independent sets. Specifically, we show that every $d$-regular graph on $n$ vertices with a moderate codegree bound contains a maximal independent set of size at most $(1+o(1))n (\log d)/d$, as $d$ goes to infinity, and this bound is sharp. The proof is based on a nibble method where, in each step, we sample from the hard-core model. I will also discuss applications.
This is joint work with Matthew Jenssen and Andrey Shapiro.