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)

 
 

 

Counting independent sets in triangle-free graphs


Authors: Jeff Cooper and Dhruv Mubayi
Journal: Proc. Amer. Math. Soc. 142 (2014), 3325-3334
MSC (2010): Primary 05C30, 05D10, 05D40
DOI: https://doi.org/10.1090/S0002-9939-2014-12068-5
Published electronically: June 6, 2014
MathSciNet review: 3238410
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Ajtai, Komlós, and Szemerédi proved that for sufficiently large $ t$ every triangle-free graph with $ n$ vertices and average degree $ t$ has an independent set of size at least $ \frac {n}{100t}\log {t}$. We extend this by proving that the number of independent sets in such a graph is at least

$\displaystyle 2^{\frac {1}{2400}\frac {n}{t}\log ^2{t}}. $

This result is sharp for infinitely many $ t,n$ apart from the constant. An easy consequence of our result is that there exists $ c'>0$ such that every $ n$-vertex triangle-free graph has at least

$\displaystyle 2^{c'\sqrt n \log n} $

independent sets. We conjecture that the exponent above can be improved to $ \sqrt {n}(\log {n})^{3/2}$. This would be sharp by the celebrated result of Kim which shows that the Ramsey number $ R(3,k)$ has order of magnitude $ k^2/\log k$.

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 (82a:05064), https://doi.org/10.1016/0097-3165(80)90030-8
  • [2] Miklós Ajtai, János Komlós, and Endre Szemerédi, A dense infinite Sidon sequence, European J. Combin. 2 (1981), no. 1, 1-11. MR 611925 (83f:10056)
  • [3] Noga Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), no. 2, 247-256. MR 1135215 (92k:11024), https://doi.org/10.1007/BF02772952
  • [4] Tom Bohman, The triangle-free process, Adv. Math. 221 (2009), no. 5, 1653-1677. MR 2522430 (2010h:05271), https://doi.org/10.1016/j.aim.2009.02.018
  • [5] P. Erdös and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087-1091. MR 0018807 (8,333b)
  • [6] 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 (2010m:05217), https://doi.org/10.1016/j.disc.2009.06.031
  • [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 (2003a:05111), https://doi.org/10.1017/S0963548301004631
  • [8] 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 (96m:05140), https://doi.org/10.1002/rsa.3240070302
  • [9] V. Nikiforov, The number of cliques in graphs of given order and size, Trans. Amer. Math. Soc. 363 (2011), no. 3, 1599-1618. MR 2737279 (2012g:05106), https://doi.org/10.1090/S0002-9947-2010-05189-X
  • [10] Alexander A. Razborov, On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), no. 4, 603-618. MR 2433944 (2009i:05118), https://doi.org/10.1017/S0963548308009085
  • [11] Christian Reiher, Minimizing the number of cliques in graphs of given order and edge density, Manuscript (2012).
  • [12] James B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983), no. 1, 83-87. MR 708165 (85b:05158), https://doi.org/10.1016/0012-365X(83)90273-X
  • [13] Paul Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436-452 (Hungarian, with German summary). MR 0018405 (8,284j)
  • [14] Yufei Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), no. 2, 315-320. MR 2593625 (2011e:05200), https://doi.org/10.1017/S0963548309990538

Similar Articles

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

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


Additional Information

Jeff Cooper
Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607
Email: jcoope8@uic.edu

Dhruv Mubayi
Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607
Email: mubayi@math.uic.edu

DOI: https://doi.org/10.1090/S0002-9939-2014-12068-5
Received by editor(s): November 15, 2011
Received by editor(s) in revised form: October 11, 2012
Published electronically: June 6, 2014
Additional Notes: The research of the second author was supported in part by NSF grant DMS 0969092.
Communicated by: Jim Haglund
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society