2016/06/30 by Ewan Davies, Matthew Jenssen, Will Perkins +1 · 1 citation
Computer Science · Mathematics · #Combinatorics #Complexity and Algorithms in Graphs #Degree (music) #Discrete mathematics #Exponent #Graph #Independent set #Lambda #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Physics #Random graph #Upper and lower bounds #math.CO
paper · pdf · doi:10.1090/proc/13728
arxiv created 2017/03/06 · openalex publication_date 2017/03/29 · arxiv updated 2018/01/25 · openalex created_date 2020/11/23 · openalex updated_date 2026/08/05
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+od(1)) \frac log ddn. 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 [ (\frac 12+od(1) ) \frac log 2 ddn ]. 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 λ |I|, for a fugacity parameter λ >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 λ =Od(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.