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