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

Abstract

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.

References in corpus (1)

• Hard constraints and the bethe lattice: adventures at the interface of combinatorics and statistical physics

Cited by in corpus (12)

• On the hard sphere model and sphere packings in high dimensions
• Extremal regular graphs: independent sets and graph homomorphisms
• Colouring triangle-free graphs with local list sizes
• Extremes of the internal energy of the Potts model on cubic graphs
• The number of independent sets in an irregular graph
• An algorithmic framework for colouring locally sparse graphs
• Counting proper colourings in 4-regular graphs via the Potts model
• Tight bounds on the coefficients of partition functions via stability
• Counting colorings of triangle-free graphs
• Counting independent sets in structured graphs
• $PC$-polynomial of graph
• The average size of independent sets of graphs