Two extensions of Ramsey's theorem
From MaRDI portal
Abstract: Ramsey's theorem, in the version of ErdH{o}s and Szekeres, states that every 2-coloring of the edges of the complete graph on {1, 2,...,n} contains a monochromatic clique of order 1/2log n. In this paper, we consider two well-studied extensions of Ramsey's theorem. Improving a result of R"odl, we show that there is a constant such that every 2-coloring of the edges of the complete graph on {2, 3,...,n} contains a monochromatic clique S for which the sum of 1/log i over all vertices i in S is at least clogloglog n. This is tight up to the constant factor c and answers a question of ErdH{o}s from 1981. Motivated by a problem in model theory, V"a"an"anen asked whether for every k there is an n such that the following holds. For every permutation pi of 1,...,k-1, every 2-coloring of the edges of the complete graph on {1, 2, ..., n} contains a monochromatic clique a_1<...<a_k with a_{pi(1)+1}-a_{pi(1)}>a_{pi(2)+1}-a_{pi(2)}>...>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, ErdH{o}s, Hajnal and Pach 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 Shelah, who showed that n is at most double-exponential in k.
Recommendations
- Two remarks on Ramsey's theorem
- Two Conjectures in Ramsey--Turán Theory
- Two results on Ramsey-Turán theory
- A Ramsey-style extension of a theorem of Erdős and Hajnal
- Some Ramsey-type theorems
- scientific article; zbMATH DE number 2058397
- Ramsey-type theorems
- On two problems in Ramsey-Turán theory
- Ramsey-Theory and Forcing Extensions
- Extensions of Gallai-Ramsey results
Cites work
- A few remarks on Ramsey--Turán-type problems
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- A new upper bound for diagonal Ramsey numbers
- Combinatorial Theorems on Classifications of Subsets of a Given Set
- Dependent random choice
- scientific article; zbMATH DE number 1109359 (Why is no real title available?)
- scientific article; zbMATH DE number 970808 (Why is no real title available?)
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- Hypergraph Ramsey numbers
- On a metric generalization of Ramsey's theorem
- On graphs with small Ramsey numbers
- On homogeneous sets of positive integers
- On the combinatorial problems which I would most like to see solved
- On two problems in graph Ramsey theory
- Partition relations for cardinal numbers
- Some remarks on the theory of graphs
- The Ramsey number of a graph with bounded maximum degree
Cited in
(6)- On homogeneous sets of positive integers
- Two average value theorems on the Ramsey problem and an initial exploration of their applications
- An additive version of Ramsey's theorem
- Two Conjectures in Ramsey--Turán Theory
- On the Mikusiński-Antosik diagonal theorem and the equivalence of two types of convergence in Köthe spaces
- scientific article; zbMATH DE number 970808 (Why is no real title available?)
This page was built for publication: Two extensions of Ramsey's theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394821)
