Maximal independent sets in clique-free graphs. (December 2022)

• Record Type: Journal Article
• Authors: He, Xiaoyu; Nie, Jiaxi; Spiro, Sam
• Is Part Of: European journal of combinatorics. Volume 106(2022)
• Publication Date: 2022-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2022.103575
• Languages: English
• ISSNs: 0195-6698

Abstract

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 .