TY - JOUR
T1 - Minimizing the number of independent sets in triangle-free regular graphs
AU - Cutler, Jonathan
AU - Radcliffe, A. J.
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2018/3
Y1 - 2018/3
N2 - 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.
AB - 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.
KW - Hard-core model
KW - Independent sets
KW - Occupancy fraction
UR - http://www.scopus.com/inward/record.url?scp=85038843125&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2017.11.016
DO - 10.1016/j.disc.2017.11.016
M3 - Article
AN - SCOPUS:85038843125
SN - 0012-365X
VL - 341
SP - 793
EP - 800
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 3
ER -