Minimizing the number of independent sets in triangle-free regular graphs

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Recently, Davies, Jenssen, Perkins, and Roberts gave a very nice proof of the result (due, in various parts, to Kahn, Galvin–Tetali, and Zhao) that the independence polynomial of a d-regular graph is maximized by disjoint copies of Kd,d. Their proof uses linear programming bounds on the distribution of a cleverly chosen random variable. In this paper, we use this method to give lower bounds on the independence polynomial of regular graphs. We also give a new bound on the number of independent sets in triangle-free cubic graphs.

Original languageEnglish
Pages (from-to)793-800
Number of pages8
JournalDiscrete Mathematics
Volume341
Issue number3
DOIs
Publication statusPublished - Mar 2018

    Fingerprint

Keywords

  • Hard-core model
  • Independent sets
  • Occupancy fraction

Cite this