Counting independent sets in triangle-free graphs

Content Provider	Semantic Scholar
Author	Cooper, Jeff Mubayi, Dhruv
Copyright Year	2011
Abstract	Ajtai, Komlós, and Szemerédi proved that for sufficiently large t every trianglefree graph with n vertices and average degree t has an independent set of size at least n 100t log t. We extend this by proving that the number of independent sets in such a graph is at least 2 1 2400 n t log . 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 2 ′n logn independent sets. We conjecture that the exponent above can be improved to √ 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 k2/ log k.
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://homepages.math.uic.edu/~mubayi/papers/indsetfinal.pdf
Language	English
Access Restriction	Open
Subject Keyword	Graph - visual representation Independent set (graph theory) Ramsey's theorem Vertex
Content Type	Text
Resource Type	Article