Stability for maximal independent sets (Q2309229)

Summary: Answering questions of Y. Rabinovich, we prove ``stability'' versions of upper bounds on maximal independent set counts in graphs under various restrictions. Roughly these say that being close to the maximum implies existence of a large induced matching or triangle matching (depending on assumptions). A mild strengthening of one of these results is a key ingredient in a proof (to appear elsewhere) of a conjecture of \textit{L. Ilinca} and \textit{J. Kahn} [Order 30, No. 2, 427--435 (2013; Zbl 1297.06005)] giving asymptotics for the number of maximal independent sets in the graph of the Hamming cube.