×

Two extensions of Ramsey’s theorem. (English) Zbl 1280.05083

Summary: Ramsey’s theorem, in the version of P. Erdős and G. Szekeres [Compos. Math. 2, 463–470 (1935; Zbl 0012.27010)], states that every 2-coloring of the edges of the complete graph on \(\{1,2,\ldots,n\}\) contains a monochromatic clique of order \((1/2)\log n\).
In this article, we consider two well-studied extensions of Ramsey’s theorem. Improving a result of V. Rödl [J. Comb. Theory, Ser. A 102, No. 1, 229–240 (2003; Zbl 1015.05091)], we show that there is a constant \(c>0\) such that every 2-coloring of the edges of the complete graph on \(\{2,3, \ldots, n\}\) contains a monochromatic clique \(S\) for which the sum of \(1/\log i\) over all vertices \(i\in S\) is at least \(c\log\log\log n\). This is tight up to the constant factor \(c\) and answers a question of P. Erdős from [Combinatorica 1, 25–42 (1981; Zbl 0486.05001)]. Motivated by a problem in model theory, Väänänen asked [J. Nešetřil and J. A. Väänänen, Commentat. Math. Univ. Carol. 37, No. 3, 433–443 (1996; Zbl 0881.05096)] whether for every \(k\) there is an \(n\) such that the following holds: for every permutation \({\pi}\) of \(\{1, \ldots,k-1\}\), every 2-coloring of the edges of the complete graph on \(\{1,2,\ldots,n\}\) contains a monochromatic clique \(a_1<\cdots< a_k\) with
\[ a_{\pi(1)+1}-a_{\pi(1)}>a_{\pi(2)+1}-a_{\pi(2)}>\cdots>a_{\pi(k-1)+1}-a_{\pi(k-1)}. \]
That is, not only do we want a monochromatic clique, but the differences between consecutive vertices must satisfy a prescribed order. Alon and, independently, P. Erdős et al. [Isr. J. Math. 102, 283–295 (1997; Zbl 0884.05092)] answered this question affirmatively. Alon further conjectured that the true growth rate should be exponential in \(k\). We make progress towards this conjecture, obtaining an upper bound on \(n\) which is exponential in a power of \(k\). This improves a result of S. Shelah [Algorithms Comb. 14, 240–246 (1997; Zbl 0864.05082)], who showed that \(n\) is at most double-exponential in \(k\).

MSC:

05C55 Generalized Ramsey theory
05D10 Ramsey theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] V. Chvatál, 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-243. · Zbl 0547.05044
[2] D. Conlon, A new upper bound for diagonal Ramsey numbers , Ann. of Math. (2) 170 (2009), 941-960. · Zbl 1188.05087
[3] D. Conlon, J. Fox, and B. Sudakov, Hypergraph Ramsey numbers , J. Amer. Math. Soc. 23 (2010), 247-266. · Zbl 1287.05087
[4] D. Conlon, J. Fox and B. Sudakov, On two problems in graph Ramsey theory , Combinatorica 32 (2012), 513-535. · Zbl 1289.05332
[5] P. Erdős, Some remarks on the theory of graphs , Bull. Amer. Math. Soc. 53 (1947), 292-294. · Zbl 0032.19203
[6] P. Erdős, On the combinatorial problems which I would most like to see solved , Combinatorica 1 (1981), 25-42. · Zbl 0486.05001
[7] P. Erdős, A. Hajnal, and J. Pach, On a metric generalization of Ramsey’s theorem , Israel J. Math. 102 (1997), 283-295. · Zbl 0884.05092
[8] P. Erdős, A. Hajnal, and R. Rado, Partition relations for cardinal numbers , Acta Math. Hungar. 16 (1965), 93-196. · Zbl 0158.26603
[9] P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set , Proc. Lond. Math. Soc. (3) 2 (1952), 417-439. · Zbl 0048.28203
[10] P. Erdős and G. Szekeres, A combinatorial problem in geometry , Compos. Math. 2 (1935), 463-470. · Zbl 0012.27010
[11] J. Fox and B. Sudakov, Dependent random choice , Random Structures Algorithms 38 (2011), 68-99. · Zbl 1215.05159
[12] W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four , Geom. Funct. Anal. 8 (1998), 529-551. · Zbl 0907.11005
[13] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory , 2nd ed., Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 1990.
[14] L. Harrington and J. Paris, “A mathematical incompleteness in Peano arithmetic” in Handbook of Mathematical Logic , Stud. Logic Found. Math. 90 , North-Holland, Amsterdam, 1977, 1133-1142.
[15] A. V. Kostochka and V. Rödl, On graphs with small Ramsey numbers , J. Graph Theory 37 (2001), 198-204. · Zbl 0994.05094
[16] J. Nešetřil and J. A. Väänänen, Combinatorics and quantifiers , Comment. Math. Univ. Carolin. 37 (1996), 433-443. · Zbl 0881.05096
[17] F. P. Ramsey, On a problem in formal logic , Proc. London Math. Soc. 30 (1930), 264-286. · JFM 55.0032.04
[18] V. Rödl, On homogeneous sets of positive integers , J. Combin. Theory Ser. A 102 (2003), 229-240. · Zbl 1015.05091
[19] S. Shelah, “A finite partition theorem with double exponential bound” in The Mathematics of Paul Erdős, II , Algorithms Combin. 14 , Springer, Berlin, 1997, 240-250. · Zbl 0864.05082
[20] B. Sudakov, A few remarks on Ramsey-Turán-type problems , J. Combin. Theory Ser. B 88 (2003), 99-106. · Zbl 1029.05104
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.