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 L. Ilinca and the first author giving asymptotics for the number of maximal independent sets in the graph of the Hamming cube.
@article{10_37236_8530,
author = {Jeff Kahn and Jinyoung Park},
title = {Stability for maximal independent sets},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {1},
doi = {10.37236/8530},
zbl = {1435.05156},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8530/}
}
TY - JOUR
AU - Jeff Kahn
AU - Jinyoung Park
TI - Stability for maximal independent sets
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8530/
DO - 10.37236/8530
ID - 10_37236_8530
ER -
%0 Journal Article
%A Jeff Kahn
%A Jinyoung Park
%T Stability for maximal independent sets
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8530/
%R 10.37236/8530
%F 10_37236_8530
Jeff Kahn; Jinyoung Park. Stability for maximal independent sets. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8530
