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 
 

 

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


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.