Counting independent sets in triangle-free graphs
HTML articles powered by AMS MathViewer
- by Jeff Cooper and Dhruv Mubayi PDF
- Proc. Amer. Math. Soc. 142 (2014), 3325-3334 Request permission
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 \[ 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 \[ 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
- 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
- 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, DOI 10.1016/S0195-6698(81)80014-5
- 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, DOI 10.1007/BF02772952
- Tom Bohman, The triangle-free process, Adv. Math. 221 (2009), no. 5, 1653–1677. MR 2522430, DOI 10.1016/j.aim.2009.02.018
- P. Erdös and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087–1091. MR 18807, DOI 10.1090/S0002-9904-1946-08715-7
- 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
- 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
- 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
- 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, DOI 10.1090/S0002-9947-2010-05189-X
- Alexander A. Razborov, On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), no. 4, 603–618. MR 2433944, DOI 10.1017/S0963548308009085
- Christian Reiher, Minimizing the number of cliques in graphs of given order and edge density, Manuscript (2012).
- 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
- Paul Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452 (Hungarian, with German summary). MR 18405
- 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
- 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
- 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
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3238410