Recent developments in graph Ramsey theory

doi:10.1017/CBO9781316106853.003

2 - Recent developments in graph Ramsey theory

Published online by Cambridge University Press: 05 July 2015

David Conlon ,

Jacob Fox and

Benny Sudakov

Edited by

Artur Czumaj ,

Agelos Georgakopoulos ,

Daniel Král ,

Vadim Lozin and

Oleg Pikhurko

Show author details

Artur Czumaj: Affiliation:
University of Warwick
Agelos Georgakopoulos: Affiliation:
University of Warwick
Daniel Král: Affiliation:
University of Warwick
Vadim Lozin: Affiliation:
University of Warwick
Oleg Pikhurko: Affiliation:
University of Warwick

Book contents

Get access

Summary

Abstract

Given a graph H, the Ramsey number r(H) is the smallest natural number N such that any two-colouring of the edges of KN contains a monochromatic copy of H. The existence of these numbers has been known since 1930 but their quantitative behaviour is still not well understood. Even so, there has been a great deal of recent progress on the study of Ramsey numbers and their variants, spurred on by the many advances across extremal combinatorics. In this survey, we will describe some of this progress.

1 Introduction

In its broadest sense, the term Ramsey theory refers to any mathematical statement which says that a structure of a given kind is guaranteed to contain a large well-organised substructure. There are examples of such statements in many areas, including geometry, number theory, logic and analysis. For example, a key ingredient in the proof of the Bolzano–Weierstrass theorem in real analysis is a lemma showing that any infinite sequence must contain an infinite monotone subsequence.

A classic example from number theory, proved by van der Waerden [212] in 1927, says that if the natural numbers are coloured in any fixed number of colours then one of the colour classes contains arbitrarily long arithmetic progressions. This result has many generalisations. The most famous, due to Szemerédi [206], says that any subset of the natural numbers of positive upper density contains arbitrarily long arithmetic progressions. This result has many generalisations. The most famous, due to Szemerédi [206], says that any subset of the natural numbers of positive upper density contains arbitrarily long arithmetic progressions.

Information

Type: Chapter
Information: Surveys in Combinatorics 2015 , pp. 49 - 118

DOI: https://doi.org/10.1017/CBO9781316106853.003 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

[1] M., Ajtai, J., Komlós, and E., Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), 354–360.Google Scholar

[2] P., Allen, G., Brightwell and J., Skokan, Ramsey-goodness – and otherwise, Combinatorica 33 (2013), 125–160.Google Scholar

[3] N., Alon, J., Balogh, A., Kostochka and W., Samotij, Sizes of induced subgraphs of Ramsey graphs, Combin. Probab. Comput. 18 (2009), 459–476.Google Scholar

[4] N., Alon and M., Krivelevich, Constructive bounds for a Ramsey-type problem, Graphs Combin. 13 (1997), 217–225.Google Scholar

[5] N., Alon, M., Krivelevich and B., Sudakov, Turáan numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput. 12 (2003), 477–494.Google Scholar

[6] N., Alon, M., Krivelevich and B., Sudakov, Large nearly regular induced subgraphs, SIAM J. Discrete Math. 22 (2008), 1325–1337.Google Scholar

[7] N., Alon, J., Pach, R., Pinchasi, R., Radoičić and M., Sharir, Crossing patterns of semi-algebraic sets, J. Combin. Theory Ser. A 111 (2005), 310–326.Google Scholar

[8] N., Alon, J., Pach and J., Solymosi, Ramsey-type theorems with forbidden subgraphs, Combinatorica 21 (2001), 155–170.Google Scholar

[9] N., Alon and V., Röodl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica 25 (2005), 125–141.Google Scholar

[10] N., Alon, P., Seymour and R., Thomas, A separator theorem for nonplanar graphs, J. Amer. Math. Soc. 3 (1990), 801–808.Google Scholar

[11] N., Alon and J. H., Spencer, The Probabilistic Method, 3rd edition, Wiley, 2007.

[12] M., Balko, J., Cibulka, K., Král and J., Kynčl, Ramsey numbers of ordered graphs, preprint.

[13] J., Balogh, R., Morris and W., Samotij, Independent sets in hypergraphs, to appear in J. Amer. Math. Soc.

[14] B., Barak, A., Rao, R., Shaltiel and A., Wigderson, 2-source dispersers for no(1) entropy, and Ramsey graphs beating the Frankl–Wilson construction, Ann. of Math. 176 (2012), 1483–1543.Google Scholar

[15] J., Beck, An upper bound for diagonal Ramsey numbers, Studia Sci. Math. Hungar. 18 (1983), 401–406.Google Scholar

[16] J., Beck, On size Ramsey number of paths, trees and cycles I, J. Graph Theory 7 (1983), 115–130.Google Scholar

[17] J., Beck, On size Ramsey number of paths, trees and cycles II, in Mathematics of Ramsey theory, Algorithms Combin., Vol. 5, 34–45, Springer, Berlin, 1990.

[18] J., Beck, Achievement games and the probabilistic method, in Combinatorics, Paul Erdőos is Eighty, Vol. 1, 51–78, Bolyai Soc. Math. Stud., Jáanos Bolyai Math. Soc., Budapest, 1993.

[19] E., Berger, K., Choromanski and M., Chudnovsky, Forcing large transitive subtournaments, to appear in J. Combin. Theory Ser. B.

[20] T., Bohman, The triangle-free process, Adv. Math. 221 (2009), 1653–1677.Google Scholar

[21] T., Bohman and P., Keevash, The early evolution of the H-free process, Invent. Math. 181 (2010), 291–336.Google Scholar

[22] T., Bohman and P., Keevash, Dynamic concentration of the trianglefree process, preprint.

[23] B., Bollobás and H. R., Hind, Graphs without large triangle free subgraphs, Discrete Math. 87 (1991), 119–131.Google Scholar

[24] M., Bonamy, N., Bousquet and S., Thomassé, The Erdős–Hajnal conjecture for long holes and anti-holes, preprint.

[25] N., Bousquet, A., Lagoutte and S., Thomassé, The Erdőos–Hajnal conjecture for paths and antipaths, to appear in J. Combin. Theory Ser. B.

[26] S., Brandt, Expanding graphs and Ramsey numbers, available at Freie Universitäat, Berlin preprint server, ftp://ftp.math.fuberlin.de/pub/math/publ/pre/1996/pr-a-96-24.ps.

[27] B., Bukh and B., Sudakov, Induced subgraphs of Ramsey graphs with many distinct degrees, J. Combin. Theory Ser. B 97 (2007), 612–619.Google Scholar

[28] S. A., Burr, Ramsey numbers involving graphs with long suspended paths, J. London Math. Soc. 24 (1981), 405–413.Google Scholar

[29] S. A., Burr, What can we hope to accomplish in generalized Ramsey theory?, Discrete Math. 67 (1987), 215–225.Google Scholar

[30] S. A., Burr and P., Erdős, On the magnitude of generalized Ramsey numbers for graphs, in Infinite and Finite Sets, Vol. 1 (Keszthely, 1973), 214–240, Colloq. Math. Soc. Janos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975.

[31] S. A., Burr and P., Erdős, Generalizations of a Ramsey-theoretic result of Chvátal, J. Graph Theory 7 (1983), 39–51.Google Scholar

[32] S. A., Burr, P., Erdős, R. J., Faudree, C. C., Rousseau and R. H., Schelp, Some complete bipartite graph-tree Ramsey numbers, Ann. Discrete Math. 41 (1989), 79–90.Google Scholar

[33] S. A., Burr, P., Erdős and L., Lovász, On graphs of Ramsey type, Ars Combin. 1 (1976), 167–190.Google Scholar

[34] S. A., Burr and V., Rosta, On the Ramsey multiplicity of graphs – problems and recent results, J. Graph Theory 4 (1980), 347–361.Google Scholar

[35] S., Butler, Induced-universal graphs for graphs with bounded maximum degree, Graphs Combin. 25 (2009), 461–468.Google Scholar

[36] J., Butterfield, T., Grauman, W. B., Kinnersley, K. G., Milans, C., Stocker and D. B., West, On-line Ramsey theory for bounded degree graphs, Electron. J. Combin. 18 (2011), P136.Google Scholar

[37] G., Chen and R. H., Schelp, Graphs with linearly bounded Ramsey numbers, J. Combin. Theory Ser. B 57 (1993), 138–149.Google Scholar

[38] M., Chudnovsky, The Erdőos–Hajnal conjecture – a survey, J. Graph Theory 75 (2014), 178–190.Google Scholar

[39] M., Chudnovsky and S., Safra, The Erdőos–Hajnal conjecture for bullfree graphs, J. Combin. Theory Ser. B 98 (2008), 1301–1310.Google Scholar

[40] M., Chudnovsky and P., Seymour, Excluding paths and antipaths, to appear in Combinatorica.

[41] F., Chung and R. L., Graham, Erdőos on Graphs. His Legacy of Unsolved Problems, A K Peters, Ltd., Wellesley, MA, 1998.

[42] V., Chváatal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93.Google Scholar

[43] V., Chvátal and F., Harary, Generalized Ramsey theory for graphs. III. Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335–345.Google Scholar

[44] V., Chvátal, V., Rödl, E., Szemerédi and W. T., Trotter Jr, The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), 239–239.Google Scholar

[45] D., Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. 170 (2009), 941–941.Google Scholar

[46] D., Conlon, Hypergraph packing and sparse bipartite Ramsey numbers, Combin. Probab. Comput. 18 (2009), 913–913.Google Scholar

[47] D., Conlon, On-line Ramsey numbers, SIAM J. Discrete Math. 23 (2009), 1954–1954.Google Scholar

[48] D., Conlon, On the Ramsey multiplicity of complete graphs, Combinatorica 32 (2012), 171–171.Google Scholar

[49] D., Conlon, The Ramsey number of dense graphs, Bull. Lond. Math. Soc. 45 (2013), 483–483.Google Scholar

[50] D., Conlon, J., Fox, C., Lee and B., Sudakov, Ramsey numbers of cubes versus cliques, to appear in Combinatorica.

[51] D., Conlon, J., Fox, C., Lee and B., Sudakov, The Erdős-Gyárfás problem on generalized Ramsey numbers, Proc. Lond. Math. Soc. 110 (2015), 1–1.Google Scholar

[52] D., Conlon, J., Fox, C., Lee and B., Sudakov, On the grid Ramsey problem and related questions, to appear in Int. Math. Res. Not.

[53] D., Conlon, J., Fox, C., Lee and B., Sudakov, Ordered Ramsey numbers, submitted.

[54] D., Conlon, J., Fox and B., Sudakov, Ramsey numbers of sparse hyper-graphs, Random Structures Algorithms 35 (2009), 1–1.Google Scholar

[55] D., Conlon, J., Fox and B., Sudakov, Hypergraph Ramsey numbers, J. Amer. Math. Soc. 23 (2010), 247–247.Google Scholar

[56] D., Conlon, J., Fox and B., Sudakov, An approximate version of Sidorenko's conjecture, Geom.Funct.Anal. 20 (2010), 1354–1354.Google Scholar

[57] D., Conlon, J., Fox and B., Sudakov, Large almost monochromatic subsets in hypergraphs, Israel J. Math. 181 (2011), 423–423.Google Scholar

[58] D., Conlon, J., Fox and B., Sudakov, On two problems in graph Ramsey theory, Combinatorial 32 (2012), 513–513.Google Scholar

[59] D., Conlon, J., Fox and B., Sudakov, Erdős-Hajnal-type theorems in hypergraphs, J. Combin. Theory Ser. B 102 (2012), 1142–1142.Google Scholar

[60] D., Conlon, J., Fox and B., Sudakov, Two extensions of Ramsey's theorem, Duke Math. J. 162 (2013), 2903–2903.Google Scholar

[61] D., Conlon, J., Fox and B., Sudakov, Short proofs of some extremal results, Combin. Probab. Comput. 23 (2014), 8–8.Google Scholar

[62] D., Conlon, J., Fox and B., Sudakov, Short proofs of some extremal results II, in preparation.

[63] D., Conlon, J., Fox and Y., Zhao, Extremal results in sparse pseudo-random graphs, Adv. Math. 256 (2014), 206–206.Google Scholar

[64] D., Conlon and W. T., Gowers, Combinatorial theorems in sparse random sets, submitted.

[65] D., Conlon and W. T., Gowers, An upper bound for Folkman numbers, preprint.

[66] O., Cooley, N., Fountoulakis, D., Kiihn and D., Osthus, 3-uniform hy-pergraphs of bounded degree have linear Ramsey numbers, J. Combin. Theory Ser. B 98 (2008), 484–484.Google Scholar

[67] O., Cooley, N., Fountoulakis, D., Kühn and D., Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, Combinatorica 28 (2009), 263–263.Google Scholar

[68] J., Cummings, D. Král', F., Pfender, K., Sperfeld, A., Treglown and M., Young, Monochromatic triangles in three-coloured graphs, J. Combin. Theory Ser. B 103 (2013), 489–489.Google Scholar

[69] D., Dellamonica, The size-Ramsey number of trees, Random Structures Algorithms 40 (2012), 49–49.Google Scholar

[70] W., Deuber, A generalization of Ramsey's theorem, in Infinite and Finite Sets, Vol. 1 (Keszthely, 1973), 323–332, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975.

[71] A., Dudek and D., Mubayi, On generalized Ramsey numbers for 3-uniform hypergraphs, J. Graph Theory 76 (2014), 217–217.Google Scholar

[72] A., Dudek, T., Retter and V., Rödl, On generalized Ramsey numbers of Erdős and Rogers, J. Combin. Theory Ser. B 109 (2014), 213–213.Google Scholar

[73] A., Dudek and V., Rodl, On the Folkman numberf (2, 3, 4), Exp. Math. 17 (2008), 63–63.Google Scholar

[74] A., Dudek and V., Rodl, On Ks-free subgraphs in Ks+k-free graphs and vertex Folkman numbers, Combinatorica 31 (2011), 39–39.Google Scholar

[75] R. A., Duke, H., Lefmann, and V., Riodl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM J. Comput. 24 (1995), 598–598.Google Scholar

[76] N., Eaton, Ramsey numbers for sparse graphs, Discrete Math. 185 (1998), 63–63.Google Scholar

[77] D., Eichhorn and D., Mubayi, Edge-coloring cliques with many colors on subcliques, Combinatorica 20 (2000), 441–441.Google Scholar

[78] P., Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–292.Google Scholar

[79] P., Erdős, Graph theory and probability II, Canad. J. Math. 13 (1961), 346–346.Google Scholar

[80] P., Erdős, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 459–459.Google Scholar

[81] P., Erdős, Problems and results on finite and infinite graphs, in Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), 183–192, Academia, Prague, 1975.

[82] P., Erdős, Solved and unsolved problems in combinatorics and combinatorial number theory, in Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981), Congr. Numer. 32 (1981), 49–49.Google Scholar

[83] P., Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25–25.Google Scholar

[84] P., Erdős, On some problems in graph theory, combinatorial analysis and combinatorial number theory, in Graph theory and combinatorics (Cambridge, 1983), 1–17, Academic Press, London, 1984.

[85] P., Erdős, Problems and results on graphs and hypergraphs: similar-ities and differences, in Mathematics of Ramsey theory, 12-28, Algorithms Combin., 5, Springer, Berlin, 1990.

[86] P., Erdős, On some of my favourite problems in various branches of combinatorics, in Proceedings of the Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), 69–79, Ann. Discrete Math., 51, North-Holland, Amsterdam, 1992.

[87] P., Erdős, Problems and results in discrete mathematics, Discrete Math. 136 (1994), 53–53.Google Scholar

[88] P., Erdős, R. J., Faudree, C. C., Rousseau and R. H., Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), 145–145.Google Scholar

[89] P., Erdős and R., Graham, On partition theorems for finite graphs, in Infinite and Finite Sets, Vol. 1 (Keszthely, 1973), 515–527, Colloq. Math.Soc.Jaanos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975.

[90] P., Erdős and A., Gyárfás, A variant of the classical Ramsey problem, Combinatorica 17 (1997), 459–459.Google Scholar

[91] P., Erdős and A., Hajnal, Research problems 2-3, J. Combin. Theory 2 (1967), 104–104.Google Scholar

[92] P., Erdős and A., Hajnal, On Ramsey like theorems, problems and results, in Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), 123–140, Inst. Math. Appl., Southend-on-Sea, 1972.

[93] P., Erdős and A., Hajnal, On spanned subgraphs of graphs, in Contributions to graph theory and its applications (Internat. Colloq., Oberhof, 1977), 80–96, Tech. Hochschule Ilmenau, Ilmenau, 1977.Google Scholar

[94] P., Erdős and A., Hajnal, Ramsey-type theorems, Discrete Appl. Math. 25 (1989), 37–37.Google Scholar

[95] P., Erdős, A., Hajnal and J., Pach, On a metric generalization of Ram-sey's theorem, Israel J. Math. 102 (1997), 283–283.Google Scholar

[96] P., Erdős, A., Hajnal and J., Pach, A Ramsey-type theorem for bipartite graphs, Geombinatorics 10 (2000), 64–64.Google Scholar

[97] P., Erdős, A., Hajnal and L., Pósa, Strong embeddings of graphs into colored graphs, in Infinite and Finite Sets, Vol. 1 (Keszthely, 1973), 585–595, Colloq. Math. Soc. Jaanos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975.

[98] P., Erdős, A., Hajnal and R., Rado, Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93–93.Google Scholar

[99] P., Erdős and R., Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. 3 (1952), 417–417.Google Scholar

[100] P., Erdős and C. A., Rogers, The construction of certain graphs, Canad. J. Math. 14 (1962), 702–702.Google Scholar

[101] P., Erdős and M., Simonovits, Cube-supersaturated graphs and related problems, in Progress in graph theory (Waterloo, Ont., 1982), 203–218, Academic Press, Toronto, ON, 1984.

[102] P., Erdős and G., Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935), 463–463.Google Scholar

[103] P., Erdős and E., Szemeraédi, On a Ramsey type theorem, Period. Math. Hungar. 2 (1972), 295–295.Google Scholar

[104] G., Fiz Pontiveros, S., Griffiths and R., Morris, The triangle-free process and R(3,k), preprint.

[105] G., Fiz Pontiveros, S., Griffiths, R., Morris, D., Saxton and J., Skokan, On the Ramsey number of the triangle and the cube, to appear in Combinatorica.

[106] G., Fiz Pontiveros, S., Griffiths, R., Morris, D., Saxton and J., Skokan, The Ramsey number of the clique and the hypercube, J. Lond. Math. Soc. 89 (2014), 680–680.Google Scholar

[107] J., Folkman, Graphs with monochromatic complete subgraphs in every edge coloring, SIAM J. Appl. Math. 18 (1970), 19–19.Google Scholar

[108] J., Fox, There exist graphs with super-exponential Ramsey multiplicity constant, J. Graph Theory 57 (2008), 89–89.Google Scholar

[109] J., Fox, A., Grinshpun and J., Pach, The Erdős-Hajnal conjecture for rainbow triangles, J. Combin. Theory Ser. B 111 (2015), 75–75.Google Scholar

[110] J., Fox and J., Pach, Erdős–Hajnal-type results on intersection patterns of geometric objects, in Horizons of combinatorics, 79–103, Bolyai Soc. Math. Stud., 17, Springer, Berlin, 2008.

[111] J., Fox and J., Pach, Applications of a new separator theorem for string graphs, Combin. Probab. Comput. 23 (2014), 66–66.Google Scholar

[112] J., Fox, J., Pach, B., Sudakov and A., Suk, Erdős-Szekeres-type theorems for monotone paths and convex bodies, Proc. Lond. Math. Soc. 105 (2012), 953–953.Google Scholar

[113] J., Fox, J., Pach and Cs. D., Tóth, Intersection patterns of curves, J. Lond. Math. Soc. 83 (2011), 389–389.Google Scholar

[114] J., Fox and B., Sudakov, Induced Ramsey-type theorems, Adv. Math. 219 (2008), 1771–1771.Google Scholar

[115] J., Fox and B., Sudakov, Ramsey-type problem for an almost monochromatic K4, SIAM J. Discrete Math. 23 (2008/09), 155-162.

[116] J., Fox and B., Sudakov, Density theorems for bipartite graphs and related Ramsey-type results, Combinatorica 29 (2009), 153–153.Google Scholar

[117] J., Fox and B., Sudakov, Two remarks on the Burr-Erdős conjecture, European J. Combin. 30 (2009), 1630–1630.Google Scholar

[118] J., Fox and B., Sudakov, Dependent Random Choice, Random Struc-tures Algorithms 38 (2011), 68–68.Google Scholar

[119] P., Frankl and V., Rödl, Large triangle-free subgraphs in graphs with-out K4, Graphs Combin. 2 (1986), 135–135.Google Scholar

[120] P., Frankl and R. M., Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357–357.Google Scholar

[121] E., Friedgut, V., Rödl and M., Schacht, Ramsey properties of discrete random structures, Random Structures Algorithms 37 (2010), 407–407.Google Scholar

[122] J., Friedman and N., Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), 71–71.Google Scholar

[123] C., Godsil and G., Royle, Algebraic Graph Theory, Springer, 2001.

[124] A. W., Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–778.Google Scholar

[125] W. T., Gowers, A new proof of Szemeraédi's theorem for arithmetic progressions of length four, Geom.Funct.Anal. 8 (1998), 529–529.Google Scholar

[126] W. T., Gowers, Hypergraph regularity and the multidimensional Szemeraedi theorem, Ann. of Math. 166 (2007), 897–897.Google Scholar

[127] R. L., Graham and V., Rödl, Numbers in Ramsey theory, in Surveys in Combinatorics 1987, 111–153, London Math. Soc. Lecture Note Ser., Vol. 123, Cambridge University Press, Cambridge, 1987.

[128] R. L., Graham, V., Rödl and A., Ruciński, On graphs with linear Ramsey numbers, J. Graph Theory 35 (2000), 176–176.Google Scholar

[129] R. L., Graham, V., Rödl and A., Ruciński, On bipartite graphs with linear Ramsey numbers, Combinatorica 21 (2001), 199–199.Google Scholar

[130] R. L., Graham, B. L., Rothschild and J. H., Spencer, Ramsey theory, 2nd edition, Wiley, 1990.

[131] B., Green and T., Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. 167 (2008), 481–481.Google Scholar

[132] J. A., Grytczuk, M., Hałuszczak and H. A., Kierstead, On-line Ramsey theory, Electron. J. Combin. 11 (2004), Research Paper 60, 10pp.Google Scholar

[133] A., Gyárfás, On a Ramsey type problem of Shelah, in Extremal prob-lems for finite sets (Visegrád, 1991), 283–287, Bolyai Soc. Math. Stud., 3, Jaanos Bolyai Math. Soc., Budapest, 1994.

[134] A., Hajnal, Rainbow Ramsey theorems for colorings establishing negative partition relations, Fund. Math. 198 (2008), 255–255.Google Scholar

[135] L., Harrington and J., Paris, A mathematical incompleteness in Peano arithmetic, in Handbook of Mathematical Logic, 1133–1142, North-Holland, Amsterdam, 1977.

[136] H., Hatami, J., Hladký, D. Král', S., Norine and A., Razborov, Non-three-colorable common graphs exist, Combin. Probab. Comput. 21 (2012), 734–734.Google Scholar

[137] P. E., Haxell, Y., Kohayakawa and T., Łuczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput. 4 (1995), 217–217.Google Scholar

[138] P., Horn, K. G., Milans and V., Rödl, Degree Ramsey numbers of closed blowups of trees, Electron. J. Combin. 21 (2014), Paper 2.5, 6pp.Google Scholar

[139] C., Jagger, P., Štovíček and A., Thomason, Multiplicities of subgraphs, Combinatorica 16 (1996), 123–123.Google Scholar

[140] H. A., Kierstead and G., Konjevod, Coloring number and on-line Ramsey theory for graphs and hypergraphs, Combinatorica, 29 (2009), 49–49.Google Scholar

[141] J. H., Kim, The Ramsey number R(3, t) has order of magnitude t2/ log t, Random Structures Algorithms 7 (1995), 173–173.Google Scholar

[142] J. H., Kim, C., Lee and J., Lee, Two approaches to Sidorenko's conjecture, to appear in Trans. Amer. Math. Soc.

[143] W. B., Kinnersley, K. G., Milans and D. B., West, Degree Ramsey numbers of graphs, Combin. Probab. Comput. 21 (2012), 229–229.Google Scholar

[144] Y., Kohayakawa, H., Prömel and V., Rödl, Induced Ramsey numbers, Combinatorica 18 (1998), 373–373.Google Scholar

[145] Y., Kohayakawa, V., Rödl, M., Schacht and E., Szemeraédi, Sparse partition universal graphs for graphs of bounded degree, Adv. Math. 226 (2011), 5041–5041.Google Scholar

[146] A. V., Kostochka and D., Mubayi, When is an almost monochromatic K4 guaranteed?Combin. Probab. Comput. 17 (2008), 823–823.Google Scholar

[147] A. V., Kostochka and V., Rödl, On graphs with small Ramsey numbers, J. Graph Theory 37 (2001), 198–198.Google Scholar

[148] A. V., Kostochka and V., Rödl, On Ramsey numbers of uniform hy-pergraphs with given maximum degree, J. Combin. Theory Ser. A 113 (2006), 1555–1555.Google Scholar

[149] A. V., Kostochka and B., Sudakov, On Ramsey numbers of sparse graphs, Combin. Probab. Comput. 12 (2003), 627–627.Google Scholar

[150] M., Krivelevich, Bounding Ramsey numbers through large deviation inequalities, Random Structures Algorithms 7 (1995), 145–145.Google Scholar

[151] M., Krivelevich and B., Sudakov, Pseudo-random graphs, in More sets, graphs and numbers, 199–262, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006.

[152] A., Kurek and A., Ruciński, Two variants of the size Ramsey number, Discuss. Math. Graph Theory 25 (2005), 141–141.Google Scholar

[153] A. R., Lange, S. P., Radziszowski and X., Xu, Use of MAX-CUT for Ramsey arrowing of triangles, J. Combin. Math. Combin. Comput. 88 (2014), 61–61.Google Scholar

[154] D., Larman, J., Matoušek, J., Pach and J., Törőcsik, A Ramsey-type result for convex sets, Bull. London Math. Soc. 26 (1994), 132–132.Google Scholar

[155] J. L. X., Li and B., Szegedy, On the logarithmic calculus and Sidorenko's conjecture, to appear in Combinatorica.

[156] L., Lu, Explicit construction of small Folkman graphs, SIAM J. Discrete Math. 21 (2007), 1053–1053.Google Scholar

[157] T., Łuczak and V., Rödl, On induced Ramsey numbers for graphs with bounded maximum degree, J. Combin. Theory Ser. B 66 (1996), 324–324.Google Scholar

[158] W., Mader, Homomorphiesätze für Graphen, Math. Ann. 178 (1968), 154–154.Google Scholar

[159] K. G., Milans, D., Stolee and D. B., West, Ordered Ramsey theory and track representations of graphs, to appear in J. Combin.

[160] G., Mills, Ramsey–Paris–Harrington numbers for graphs, J. Combin. Theory Ser. A 38 (1985), 30–30.Google Scholar

[161] G., Moshkovitz and A., Shapira, Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem, Adv. Math. 262 (2014), 1107–1107.Google Scholar

[162] D., Mubayi, Edge-coloring cliques with three colors on all 4-cliques, Combinatorica 18 (1998), 293–293.Google Scholar

[163] B., Nagle, S., Olsen, V., Rödl and M., Schacht, On the Ramsey number of sparse 3-graphs, Graphs Combin. 27 (2008), 205–205.Google Scholar

[164] B., Nagle, V., Rödl and M., Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms 28 (2006), 113–179.Google Scholar

[165] R., Nenadov and A., Steger, A short proof of the random Ramsey theorem, to appear in Combin. Probab. Comput.

[166] J., Nesetril and V., Rödl, The Ramsey property for graphs with forbidden complete subgraphs, J. Combin. Theory Ser. B 20 (1976), 243–243.Google Scholar

[167] J., Nešetřil and V., Rödl, Simple proof of the existence of restricted Ramsey graphs by means of a partite construction, Combinatorica 1 (1981), 199–199.Google Scholar

[168] J., Nešetřil and J. A., Väänänen, Combinatorics and quantifiers, Comment. Math. Univ. Carolin. 37 (1996), 433–433.Google Scholar

[169] S., Nieβ, Counting monochromatic copies of K4: a new lower bound for the Ramsey multiplicity problem, preprint.

[170] V., Nikiforov and C. C., Rousseau, Ramsey goodness and beyond, Combinatorica 29 (2009), 227–227.Google Scholar

[171] N., Paul and C., Tardif, The chromatic Ramsey number of odd wheels, J. Graph Theory 69 (2012), 198–198.Google Scholar

[172] H., Prömel and V., Rödl, Non-Ramsey graphs are c log n-universal, J. Combin. Theory Ser. A 88 (1999), 379–379.Google Scholar

[173] S., Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2014), DS1.

[174] F. P., Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264–264.Google Scholar

[175] A. A., Razborov, Flag algebras, J. Symbolic Logic 72 (2007), 1239–1282.Google Scholar

[176] V., Rödl, The dimension of a graph and generalized Ramsey theorems, Master's thesis, Charles University, 1973.

[177] V., Rödl, On universality of graphs with uniformly distributed edges, Discrete Math. 59 (1986), 125–125.Google Scholar

[178] V., Rödl, On homogeneous sets of positive integers, J. Combin. Theory Ser. A 102 (2003), 229–229.Google Scholar

[179] V., Rödl and A., Ruciński, Lower bounds on probability thresholds for Ramsey properties, in Combinatorics, Paul Erdős is eighty, Vol. 1, 317–346, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993.

[180] V., Rödl and A., Ruciński, Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), 917–917.Google Scholar

[181] V., Rödl, A., Ruciński and M., Schacht, An exponential-type upper bound for Folkman numbers, preprint.

[182] V., Rödl and M., Schacht, Complete partite subgraphs in dense hypergraphs, Random Structures Algorithms 41 (2012), 557–557.Google Scholar

[183] V., Rödl and J., Skokan, Regularity lemma for uniform hypergraphs, Random Structures Algorithms 25 (2004), 1–1.Google Scholar

[184] V., Rödl and E., Szemernédi, On size Ramsey numbers of graphs with bounded maximum degree, Combinatorica 20 (2000), 257–257.Google Scholar

[185] V., Rödl and R., Thomas, Arrangeability and clique subdivisions, in The mathematics of Paul Erdős, II, 236–239, Algorithms Combin., 14, Springer, Berlin, 1997.Google Scholar

[186] G. N., Sárkozy and S. M., Selkow, On edge colorings with at least q colors in every subset of p vertices, Electron.J.Combin. 8 (2001), Research Paper 9, 6pp.Google Scholar

[187] G. N., Sárközy and S. M., Selkow, An application of the regularity lemma in generalized Ramsey theory, J. Graph Theory 44 (2003), 39–39.Google Scholar

[188] D., Saxton and A., Thomason, Hypergraph containers, to appear in Invent. Math.

[189] M., Schacht, Extremal results for discrete random structures, preprint.

[190] J., Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983), 83–83.CrossRef Google Scholar

[191] J., Shearer, On the independence number of sparse graphs, Random Structures Algorithms 7 (1995), 269–269.Google Scholar

[192] S., Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1989), 683–683.CrossRef Google Scholar

[193] S., Shelah, A finite partition theorem with double exponential bound, in The mathematics of Paul Erdős, II, 240–246, Algorithms Combin., 14, Springer, Berlin, 1997.

[194] L., Shi, Cube Ramsey numbers are polynomial, Random Structures Algorithms 19 (2001), 99–99.Google Scholar

[195] L., Shi, The tail is cut for Ramsey numbers of cubes, Discrete Math. 307 (2007), 290–290.CrossRef Google Scholar

[196] A. F., Sidorenko, Cycles in graphs and functional inequalities, Math. Notes 46 (1989), 877–877.CrossRef Google Scholar

[197] A. F., Sidorenko, A correlation inequality for bipartite graphs, Graphs Combin. 9 (1993), 201–201.CrossRef Google Scholar

[198] J. H., Spencer, Ramsey's theorem – a new lower bound, J. Combin. Theory Ser. A 18 (1975), 108–108.Google Scholar

[199] J. H., Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math. 20 (1977/78), 69–76.Google Scholar

[200] J. H., Spencer, Three hundred million points suffice, J. Combin. The-ory Ser. A 49 (1988), 210–210. See also the erratum by M. Hovey in J. Combin. Theory Ser. A 50 (989), 323.Google Scholar

[201] K., Sperfeld, On the minimal monochromatic K4-density, preprint.

[202] B., Sudakov, A few remarks on the Ramsey-Turán-type problems, J. Combin. Theory Ser. B 88 (2003), 99–99.Google Scholar

[203] B., Sudakov, A new lower bound for a Ramsey-type problem, Combinatorica 25 (2005), 487–487.Google Scholar

[204] B., Sudakov, Large Kr-free subgraphs in Ks-free graphs and some other Ramsey-type problems, Random Structures Algorithms 26 (2005), 253–253.Google Scholar

[205] B., Sudakov, A conjecture of Erdős on graph Ramsey numbers, Adv. Math. 227 (2011), 601–601.Google Scholar

[206] E., Szemernédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–199.Google Scholar

[207] E., Szemeredi, Regular partitions of graphs, in Problémes Combinatoires et Théorie des Graphes (Orsay 1976), 399–401, Colloq. Internat. CNRS, 260, CNRS, Paris, 1978.

[208] A., Thomason, Pseudorandom graphs, in Random graphs '85 (Poznań, 1985), 307–331, North-Holland Math. Stud., Vol. 144, NorthHolland, Amsterdam, 1987.

[209] A., Thomason, Random graphs, strongly regular graphs and pseudorandom graphs, in Surveys in Combinatorics 1987, 173–195, London Math. Soc. Lecture Note Ser., Vol. 123, Cambridge University Press, Cambridge, 1987.

[210] A., Thomason, An upper bound for some Ramsey numbers, J. Graph Theory 12 (1988), 509–509.Google Scholar

[211] A., Thomason, A disproof of a conjecture of Erdos in Ramsey theory, J. London Math. Soc. 39 (1989), 246–246.Google Scholar

[212] B. L., van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wish. 15 (1927), 212–212.Google Scholar

[213] G., Wolfovitz, K4-free graphs without large induced triangle-free subgraphs, Combinatorica 33 (2013), 623–623.Google Scholar

[214] X., Zhu, The fractional version of Hedetniemi's conjecture is true, European J. Combin. 32 (2011), 1168–1168.Google Scholar

Accessibility standard: Unknown

Why this information is here

This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.

Accessibility Information

Accessibility compliance for the PDF of this chapter is currently unknown and may be updated in the future.