×

Counting independent sets in triangle-free graphs. (English) Zbl 1300.05169

Summary: M. Ajtai et al. [J. Comb. Theory, Ser. A 29, 354–360 (1980; Zbl 0455.05045)] 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^2t}. \] This result is sharp for infinitely many \(t\), \(n\) apart from the constant. An easy consequence of our result is that there exists \(c^\prime>0\) such that every \(n\)-vertex triangle-free graph has at least of independent sets in such a graph is at least \[ 2^{c^\prime\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 J. H. Kim [Random Struct. Algorithms 7, No. 3, 173–207 (1995; Zbl 0832.05084)] which shows that the Ramsey number \(R(3,k)\) has order of magnitude \(k^2/\log k\).

MSC:

05C55 Generalized Ramsey theory
05C30 Enumeration in graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05D10 Ramsey theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
60C05 Combinatorial probability

Keywords:

Ramsey number

References:

[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. · Zbl 0455.05045 · doi: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. · Zbl 0474.10038 · doi:10.1016/S0195-6698(81)80014-5
[3] Noga Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), no. 2, 247 – 256. · Zbl 0762.05050 · doi:10.1007/BF02772952
[4] Tom Bohman, The triangle-free process, Adv. Math. 221 (2009), no. 5, 1653 – 1677. · Zbl 1195.05074 · doi: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. · Zbl 0063.01277
[6] David Galvin, An upper bound for the number of independent sets in regular graphs, Discrete Math. 309 (2009), no. 23-24, 6635 – 6640. · Zbl 1236.05111 · doi: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. · Zbl 0985.60088 · doi:10.1017/S0963548301004631
[8] Jeong Han Kim, The Ramsey number \?(3,\?) has order of magnitude \?²/log\?, Random Structures Algorithms 7 (1995), no. 3, 173 – 207. · Zbl 0832.05084 · doi: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. · Zbl 1231.05129
[10] Alexander A. Razborov, On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), no. 4, 603 – 618. · Zbl 1170.05036 · doi: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. · Zbl 0516.05053 · doi: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). · Zbl 0026.26903
[14] Yufei Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), no. 2, 315 – 320. · Zbl 1215.05140 · doi:10.1017/S0963548309990538
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.