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

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticle

2 Citations (Scopus)

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
StatePublished - 1 Mar 2018

Fingerprint

Triangle-free Graph
Independent Set
Regular Graph
Polynomials
Polynomial
Cubic Graph
Random variables
Linear programming
Disjoint
Random variable
Lower bound
Independence

Keywords

  • Hard-core model
  • Independent sets
  • Occupancy fraction

Cite this

@article{89cf69a7550f4715820925a757187e8b,
title = "Minimizing the number of independent sets in triangle-free regular graphs",
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.",
keywords = "Hard-core model, Independent sets, Occupancy fraction",
author = "Jonathan Cutler and Radcliffe, {A. J.}",
year = "2018",
month = "3",
day = "1",
doi = "10.1016/j.disc.2017.11.016",
language = "English",
volume = "341",
pages = "793--800",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "3",

}

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

In: Discrete Mathematics, Vol. 341, No. 3, 01.03.2018, p. 793-800.

Research output: Contribution to journalArticle

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 -