The critical window for the classical Ramsey-Turán problem

详细信息    查看全文

• 作者：Jacob Fox ; Po-Shen Loh ; Yufei Zhao
• 关键词：05C35 ; 05C55 ; 05D40
• 刊名：Combinatorica
• 出版年：2015
• 出版时间：August 2015
• 年：2015
• 卷：35
• 期：4
• 页码：435-476
• 全文大小：617 KB
• 参考文献：[1] N. Alon and J. Spencer : The probabilistic method, 3rd ed., John Wiley & Sons Inc., Hoboken, NJ (2008).CrossRef MATH
  [2] K. Ball : An elementary introduction to modern convex geometry, in: Flavors of geometry, Math. Sci. Res. Inst. Publ. 31, Cambridge Univ. Press, Cambridge, 1997, 1-8.
  [3] J. Balogh and J. Lenz : On the Ramsey-Turán numbers of graphs and hypergraphs, Israel J. Math. 194 (2013), 45-8.CrossRef MathSciNet MATH
  [4] J. Balogh and J. Lenz : Some exact Ramsey-Turán numbers, Bull. Lond. Math. Soc. 44 (2012), 1251-258.CrossRef MathSciNet MATH
  [5] B. Bollobás and P. Erd?s : On a Ramsey-Turán type problem, J. Combin. Theory Ser. B. 21 (1976), 166-68.CrossRef MATH
  [6] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós and K. Vesztergombi : Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), 1801-851.CrossRef MathSciNet MATH
  [7] P. Chau, L. DeBiasio and H. A. Kierstead : Pósa’s conjecture for graphs of order at least 2 × 108, Random Structures Algorithms 39 (2011), 507-25.CrossRef MathSciNet MATH
  [8] D. Conlon : Hypergraph packing and sparse bipartite Ramsey numbers, Combin. Probab. Comput., 18 (2009), 913-23.CrossRef MathSciNet MATH
  [9] D. Conlon and J. Fox : Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), 1191-256.CrossRef MathSciNet MATH
  [10] D. Conlon, J. Fox and B. Sudakov : On two problems in graph Ramsey theory, Combinatorica 32 (2012), 513-35.CrossRef MathSciNet MATH
  [11] P. Erd?s : Some recent results on extremal problems in graph theory. Results, in: Theory of Graphs (Internat. Sympos., Rome, 1966), Gordon and Breach, New York, 1967, 117-23.
  [12] P. Erd?s : Some of my favourite unsolved problems, in: A tribute to Paul Erd?s, Cambridge University Press, 1990, 467-78.CrossRef
  [13] P. Erd?s, A. Hajnal, V. T. Sós and E. Szemerédi : More results on Ramsey-Turán type problem, Combinatorica 3 (1983), 69-2.CrossRef MathSciNet
  [14] P. Erd?s, A. Hajnal, M. Simonovits, V. T. Sós and E. Szemerédi : Turán-Ramsey theorems and simple asymptotically extremal structures, Combinatorica 13 (1993), 31-6.CrossRef MathSciNet
  [15] P. Erd?s, A. Hajnal, M. Simonovits, V. T. Sós and E. Szemerédi : Turán- Ramsey theorems and K p-independence number, in: Combinatorics, geometry and probability (Cambridge, 1993), Cambridge Univ. Press, Cambridge, 1997, 253-81.CrossRef
  [16] P. Erd?s and V. T. Sós : Some remarks on Ramsey’s and Turán’s theorem, in: Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, 1970, 395-04.
  [17] U. Feige and G. Schechtman : On the optimality of the random hyperplane rounding technique for MAX CUT, Random Structures Algorithms 20 (2002), 403-40.CrossRef MathSciNet MATH
  [18] J. Fox : A new proof of the graph removal lemma, Ann. of Math. 174 (2011), 561-79.CrossRef MathSciNet MATH
  [19] J. Fox and B. Sudakov : Density theorems for bipartite graphs and related Ramseytype results, Combinatorica 29 (2009), 153-96.MathSciNet MATH
  [20] J. Fox and B. Sudakov : Dependent random choice, Random Structures Algorithms 38 (2011), 68-9.CrossRef MathSciNet MATH
  [21] A. Frieze and R. Kannan : The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th IEEE FOCS (1996), 12-0.
  [22] A. Frieze and R. Kannan : Quick approximation to matrices and applications, Combinatorica 19 (1999), 175-20.CrossRef MathSciNet MATH
  [23] A. W. Goodman : On sets of acquaintances and strangers at any party, American Mathematical Monthly 66 (1959), 778-83.CrossRef MathSciNet MATH
  [24] W. T. Gowers : Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal. 7 (1997), 322-37.CrossRef MathSciNet MATH
  [25] W. T. Gowers : Rough structure and classification, GAFA 2000 (Tel Aviv, 1999), Geom. Funct. Anal. 2000, Special Volume, Part I, 79-17.
  [26] W. T. Gowers : A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), 465-88.CrossRef MathSciNet MATH
  [27] R. L. Graham, V. R?dl and A. Ruciński : On graphs with linear Ramsey numbers, J. Graph Theory 35 (2000), 176-92.CrossRef MathSciNet MATH
  [28] J. Komlós and M. Simonovits : Szemerédi’s regularity lemma and its applications in graph theory, in: Combinatorics, Paul Erd?s is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest, 1996, 295-52.
  [29] J. Komlós, A. Shokoufandeh, M. Simonovits and E. Szemerédi : The regularity lemma and its applications in graph theory, in: Theoretical aspects of computer science (Tehran, 2000), Lecture Notes in Comput. Sci., 2292, Springer, Berlin, 2002, 84-12.CrossRef
  [30] I. Levitt, G. N. Sárk?zy and E. Szemerédi : How to avoid using the regularity lemma: Pósa’s conjecture revisited, Discrete Math. 310 (2010), 630-41.CrossRef MathSciNet MATH
  [31] V. R?dl and M. Schacht : Regularity lemma
• 作者单位：Jacob Fox (1)
  Po-Shen Loh (2)
  Yufei Zhao (1)
  
  1. Department of Mathematics, MIT, Cambridge, MA, 02139-4307, USA
  2. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, 15213, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Mathematics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1439-6912

文摘

The first application of Szemerédi’s powerful regularity method was the following celebrated Ramsey-Turán result proved by Szemerédi in 1972: any K ₄-free graph on n vertices with independence number o(n) has at most \((\tfrac{1} {8} + o(1))n^2\) edges. Four years later, Bollobás and Erd?s gave a surprising geometric construction, utilizing the isoperimetric inequality for the high dimensional sphere, of a K ₄-free graph on n vertices with independence number o(n) and \((\tfrac{1} {8} - o(1))n^2\) edges. Starting with Bollobás and Erd?s in 1976, several problems have been asked on estimating the minimum possible independence number in the critical window, when the number of edges is about n 2/8. These problems have received considerable attention and remained one of the main open problems in this area. In this paper, we give nearly best-possible bounds, solving the various open problems concerning this critical window. Mathematics Subject Classication (2000) 05C35 05C55 05D40