Maximal independent sets in clique-free graphs. (December 2022) - He, Xiaoyu; Nie, Jiaxi; Spiro, Sam
Abstract: Nielsen proved that the maximum number of maximal independent sets (MISs) of size k in an n -vertex graph is asymptotic to ( n / k ) k, with the extremal construction a disjoint union of k cliques with sizes as close to n / k as possible. In this paper we study how many MISs 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 ⌊ ( t − 2 ) k t − 1 ⌋ − o ( 1 ) MISs of size k by utilizing recent work of Gowers and B. Janzer on a generalization of the Ruzsa–Szemerédi problem. We prove that this bound is essentially best possible for triangle-free graphs when k ≤ 4 .