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)

Request Permissions   Purchase Content 
 
 

 

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?)

  • [1] 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, https://doi.org/10.1016/0097-3165(80)90030-8
  • [2] 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.
  • [3] Noga Alon, Independence numbers of locally sparse graphs and a Ramsey type problem, Random Structures Algorithms 9 (1996), no. 3, 271-278. MR 1606837, https://doi.org/10.1002/(SICI)1098-2418(199610)9:3$ \langle $271::AID-RSA1$ \rangle $3.0.CO;2-U
  • [4] 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
  • [5] 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, https://doi.org/10.1214/16-EJP3552
  • [6] Tom Bohman and Peter Keevash, Dynamic concentration of the triangle-free process, arXiv preprint arXiv:1302.5963 (2013).
  • [7] 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
  • [8] Jeff Cooper, Kunal Dutta, and Dhruv Mubayi, Counting independent sets in hypergraphs, Combin. Probab. Comput. 23 (2014), no. 4, 539-550. MR 3217359, https://doi.org/10.1017/S0963548314000182
  • [9] Jeff Cooper and Dhruv Mubayi, Counting independent sets in triangle-free graphs, Proc. Amer. Math. Soc. 142 (2014), no. 10, 3325-3334. MR 3238410, https://doi.org/10.1090/S0002-9939-2014-12068-5
  • [10] 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, https://doi.org/10.4171/JEMS/706
  • [11] Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, Independent sets, matchings, and occupancy fractions, preprint, arXiv:1508.04675 (2015).
  • [12] Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris, The triangle-free process and $ {R}(3, k)$, preprint, arXiv:1302.6279 (2013).
  • [13] 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, https://doi.org/10.1016/j.disc.2009.06.031
  • [14] 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, https://doi.org/10.1016/0095-8956(82)90055-7
  • [15] Jeff Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput. 10 (2001), no. 3, 219-237. MR 1841642, https://doi.org/10.1017/S0963548301004631
  • [16] 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
  • [17] 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, https://doi.org/10.1002/rsa.3240070302
  • [18] Alexandr Kostochka, Dhruv Mubayi, and Jacques Verstraëte, On independent sets in hypergraphs, Random Structures Algorithms 44 (2014), no. 2, 224-239. MR 3158630, https://doi.org/10.1002/rsa.20453
  • [19] Michael Molloy and Bruce Reed, Graph colouring and the probabilistic method, Algorithms and Combinatorics, vol. 23, Springer-Verlag, Berlin, 2002. MR 1869439
  • [20] 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 0151955
  • [21] Nicholas Ruozzi, The Bethe partition function of log-supermodular graphical models, Advances in Neural Information Processing Systems, 2012, pp. 117-125.
  • [22] James B Shearer, personal communication.
  • [23] James B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983), no. 1, 83-87. MR 708165, https://doi.org/10.1016/0012-365X(83)90273-X
  • [24] James B. Shearer, On the independence number of sparse graphs, Random Structures Algorithms 7 (1995), no. 3, 269-271. MR 1369066, https://doi.org/10.1002/rsa.3240070305
  • [25] 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.
  • [26] Yufei Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), no. 2, 315-320. MR 2593625, https://doi.org/10.1017/S0963548309990538

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