On the average size of independent sets in triangle-free graphs

By Ewan Davies, Matthew Jenssen, Will Perkins, Barnaby Roberts. 2016

62 citations recorded by the source corpus.

We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on $n$ vertices with maximum degree $d$, showing that an independent set drawn uniformly at random from such a graph has expected size at least $(1+o_d(1)) \frac{\log d}{d}n$. This gives an alternative proof of Shearer's upper bound on the Ramsey number $R(3,k)$. We then prove that the total number of independent sets in a triangle-free graph with maximum degree $d$ is at least $\exp \left[\left(\frac{1}{2}+o_d(1) \right) \frac{\log^2 d}{d}n \right]$. The constant $1/2$ in the exponent is best possible. In both cases, tightness is exhibited by a random $d$-regular graph. Both results come from considering the hard-core model from statistical physics: a random independent set $I$ drawn from a graph with probability proportional to $\lambda^{|I|}$, for a fugacity parameter $\lambda>0$. We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree $d$. The bound is asymptotically tight in $d$ for all $\lambda =O_d(1)$. We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/cf96e18b341f4eaddd3a0bf5731366866bc0fad7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

  1. Ross J. Kang
  2. Franccois Pirot
  3. Jean-Sébastien Sereni
  4. Ewan Davies

Citations in the corpus