Stability for maximal independent sets

Jeff Kahn, Jinyoung Park

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article numberP1.59
JournalElectronic Journal of Combinatorics
Volume27
Issue number1
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Stability for maximal independent sets'. Together they form a unique fingerprint.

Cite this