## 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

- Miklós Ajtai, János Komlós, and Endre Szemerédi,
*A note on Ramsey numbers*, J. Combin. Theory Ser. A**29**(1980), no. 3, 354–360. MR**600598**, DOI 10.1016/0097-3165(80)90030-8 - Vladimir E Alekseev,
*On the number of maximal independent sets in graphs from hereditary classes*, Combinatorial-Algebraic Methods in Discrete Optimization, University of Nizhny Novgorod (1991), pp. 5–8. - Noga Alon,
*Independence numbers of locally sparse graphs and a Ramsey type problem*, Random Structures Algorithms**9**(1996), no. 3, 271–278. MR**1606837**, DOI 10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U - Noga Alon and Joel H. Spencer,
*The probabilistic method*, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR**3524748** - Nayantara Bhatnagar, Allan Sly, and Prasad Tetali,
*Decay of correlations for the hardcore model on the $d$-regular random graph*, Electron. J. Probab.**21**(2016), Paper No. 9, 42. MR**3485351**, DOI 10.1214/16-EJP3552 - Tom Bohman and Peter Keevash,
*Dynamic concentration of the triangle-free process*, arXiv preprint arXiv:1302.5963 (2013). - Graham R. Brightwell and Peter Winkler,
*Hard constraints and the Bethe lattice: adventures at the interface of combinatorics and statistical physics*, Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 605–624. MR**1957564** - Jeff Cooper, Kunal Dutta, and Dhruv Mubayi,
*Counting independent sets in hypergraphs*, Combin. Probab. Comput.**23**(2014), no. 4, 539–550. MR**3217359**, DOI 10.1017/S0963548314000182 - Jeff Cooper and Dhruv Mubayi,
*Counting independent sets in triangle-free graphs*, Proc. Amer. Math. Soc.**142**(2014), no. 10, 3325–3334. MR**3238410**, DOI 10.1090/S0002-9939-2014-12068-5 - Péter Csikvári,
*Lower matching conjecture, and a new proof of Schrijver’s and Gurvits’s theorems*, J. Eur. Math. Soc. (JEMS)**19**(2017), no. 6, 1811–1844. MR**3646876**, DOI 10.4171/JEMS/706 - Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts,
*Independent sets, matchings, and occupancy fractions*, preprint, arXiv:1508.04675 (2015). - Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris,
*The triangle-free process and ${R}(3, k)$*, preprint, arXiv:1302.6279 (2013). - David Galvin,
*An upper bound for the number of independent sets in regular graphs*, Discrete Math.**309**(2009), no. 23-24, 6635–6640. MR**2558628**, DOI 10.1016/j.disc.2009.06.031 - Charles M. Grinstead and Sam M. Roberts,
*On the Ramsey numbers $R(3,\,8)$ and $R(3,\,9)$*, J. Combin. Theory Ser. B**33**(1982), no. 1, 27–51. MR**678169**, DOI 10.1016/0095-8956(82)90055-7 - Jeff Kahn,
*An entropy approach to the hard-core model on bipartite graphs*, Combin. Probab. Comput.**10**(2001), no. 3, 219–237. MR**1841642**, DOI 10.1017/S0963548301004631 - F. P. Kelly,
*Stochastic models of computer communication systems*, J. Roy. Statist. Soc. Ser. B**47**(1985), no. 3, 379–395, 415–428. With discussion. MR**844469** - Jeong Han Kim,
*The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$*, Random Structures Algorithms**7**(1995), no. 3, 173–207. MR**1369063**, DOI 10.1002/rsa.3240070302 - Alexandr Kostochka, Dhruv Mubayi, and Jacques Verstraëte,
*On independent sets in hypergraphs*, Random Structures Algorithms**44**(2014), no. 2, 224–239. MR**3158630**, DOI 10.1002/rsa.20453 - Michael Molloy and Bruce Reed,
*Graph colouring and the probabilistic method*, Algorithms and Combinatorics, vol. 23, Springer-Verlag, Berlin, 2002. MR**1869439**, DOI 10.1007/978-3-642-04016-0 - J. W. Moon and L. Moser,
*On a problem of Turán*, Magyar Tud. Akad. Mat. Kutató Int. Közl.**7**(1962), 283–286 (English, with Russian summary). MR**151955** - Nicholas Ruozzi,
*The Bethe partition function of log-supermodular graphical models*, Advances in Neural Information Processing Systems, 2012, pp. 117–125. - James B Shearer, personal communication.
- James B. Shearer,
*A note on the independence number of triangle-free graphs*, Discrete Math.**46**(1983), no. 1, 83–87. MR**708165**, DOI 10.1016/0012-365X(83)90273-X - James B. Shearer,
*On the independence number of sparse graphs*, Random Structures Algorithms**7**(1995), no. 3, 269–271. MR**1369066**, DOI 10.1002/rsa.3240070305 - Alan S. Willsky, Erik B. Sudderth, and Martin J. Wainwright,
*Loop series and Bethe variational bounds in attractive graphical models*, Advances in Neural Information Processing Systems, 2008, pp. 1425–1432. - Yufei Zhao,
*The number of independent sets in a regular graph*, Combin. Probab. Comput.**19**(2010), no. 2, 315–320. MR**2593625**, DOI 10.1017/S0963548309990538

## 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