### 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 K_{d,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 language | English |
---|---|

Pages (from-to) | 793-800 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 341 |

Issue number | 3 |

DOIs | |

State | Published - 1 Mar 2018 |

### Fingerprint

### Keywords

- Hard-core model
- Independent sets
- Occupancy fraction

### Cite this

*Discrete Mathematics*,

*341*(3), 793-800. https://doi.org/10.1016/j.disc.2017.11.016

}

*Discrete Mathematics*, vol. 341, no. 3, pp. 793-800. https://doi.org/10.1016/j.disc.2017.11.016

**Minimizing the number of independent sets in triangle-free regular graphs.** / Cutler, Jonathan; Radcliffe, A. J.

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Cutler, Jonathan

AU - Radcliffe, A. J.

PY - 2018/3/1

Y1 - 2018/3/1

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

VL - 341

SP - 793

EP - 800

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 3

ER -