Minimizing the number of independent sets in triangle-free regular graphs |
| |
Authors: | Jonathan Cutler A.J. Radcliffe |
| |
Affiliation: | 1. Department of Mathematical Sciences, Montclair State University, Montclair, NJ, United States;2. Department of Mathematics, University of Nebraska-Lincoln, Lincoln, NE, United States |
| |
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 -regular graph is maximized by disjoint copies of . 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. |
| |
Keywords: | Independent sets Occupancy fraction Hard-core model |
本文献已被 ScienceDirect 等数据库收录! |
|