Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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


Authors: Ewan Davies, Matthew Jenssen, Will Perkins and Barnaby Roberts
Journal: Proc. Amer. Math. Soc. 146 (2018), 111-124
MSC (2010): Primary 05C69; Secondary 05D10, 05D40
DOI: https://doi.org/10.1090/proc/13728
Published electronically: July 27, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 ^{\vert I\vert}$, 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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C69, 05D10, 05D40

Retrieve articles in all journals with MSC (2010): 05C69, 05D10, 05D40


Additional Information

Ewan Davies
Affiliation: Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom
Email: e.s.davies@lse.ac.uk

Matthew Jenssen
Affiliation: Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom
Email: m.o.jenssen@lse.ac.uk

Will Perkins
Affiliation: School of Mathematics, University of Birmingham, Birmingham B15 2TT, United Kingdom
Email: math@willperkins.org

Barnaby Roberts
Affiliation: Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom
Email: b.j.roberts@lse.ac.uk

DOI: https://doi.org/10.1090/proc/13728
Keywords: Independent sets, hard-core model, Ramsey theory
Received by editor(s): June 8, 2016
Received by editor(s) in revised form: March 6, 2017
Published electronically: July 27, 2017
Additional Notes: The third author was supported in part by EPSRC grant EP/P009913/1.
Communicated by: Patricia Hersh
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society