Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On the average size of independent sets in triangle-free graphs
HTML articles powered by AMS MathViewer

by Ewan Davies, Matthew Jenssen, Will Perkins and Barnaby Roberts PDF
Proc. Amer. Math. Soc. 146 (2018), 111-124 Request permission

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
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
  • MR Author ID: 1015306
  • ORCID: 0000-0003-0026-8501
  • Email: m.o.jenssen@lse.ac.uk
  • Will Perkins
  • Affiliation: School of Mathematics, University of Birmingham, Birmingham B15 2TT, United Kingdom
  • MR Author ID: 939443
  • 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
  • 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
  • © Copyright 2017 American Mathematical Society
  • Journal: Proc. Amer. Math. Soc. 146 (2018), 111-124
  • MSC (2010): Primary 05C69; Secondary 05D10, 05D40
  • DOI: https://doi.org/10.1090/proc/13728
  • MathSciNet review: 3723125