
arXiv: 1808.06666
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.
Extremal problems in graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), large induced matching, 05C69, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), triangle matching
Extremal problems in graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), large induced matching, 05C69, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), triangle matching
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
