Skip to main content

All Questions

Filter by
Sorted by
Tagged with
23 votes
1 answer
1k views

List Ramsey numbers?

The diagonal Ramsey number $R(n,n)$ is the least number $m$ for which the following holds: in any edge-colouring of the complete graph $K_m$ in which each edge is coloured blue or red, there is a ...
bof's user avatar
  • 13.4k
10 votes
3 answers
490 views

How many colors do we need to avoid bichromatic triangles?

Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors. I wonder if the following type of question has ...
domotorp's user avatar
  • 18.9k
9 votes
2 answers
441 views

From very many sets of fixed measure in a probability space, can we select many that have a positive intersection?

I assume the following Lemma is either well known or, more probably, a Corollary of a much stronger well known Theorem, and I would be grateful for a reference: For all $\delta\in (0,1)$ and all $\...
Jakob's user avatar
  • 894
7 votes
2 answers
595 views

A 2-page paper on a lower bound of Ramsey number

I'm looking for a 2-page paper on a lower bound of Ramsey number $R(a,b)$ for some constants $a$ and $b$. The paper was published in 80s or 90s. I googled it for a few days, but I cannot find the ...
Junhee Cho's user avatar
7 votes
0 answers
203 views

Primitive recursive bounds for the the Gallai-Witt theorem

Let me first recall some facts: By the work of Gowers, the Van der Waerden numbers belong to class $\mathcal{E}^3$ of the Grzegorczyk hierarchy By the work of Shelah, the Hales-Jewett numbers belong ...
Mohammad Golshani's user avatar
7 votes
0 answers
220 views

A funny kind of Ramsey number

A shorter version of this question was posted on Math Stack Exchange. Let $V$ be a nonempty set. $(V,S)$ is a graph if $S\subseteq\binom V2,$ a triple system if $S\subseteq\binom V3,$ a quadruple ...
bof's user avatar
  • 13.4k
6 votes
1 answer
457 views

Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate. Is the Van der Waerden's function itself elementary in the sense of Kalmar?
user avatar
5 votes
1 answer
310 views

A variant of Ramsey numbers

The well known Ramsey number $R(k)$ is the least integer $n$ so that every 2-edge coloring of $K_n$ contains a monochromatic $K_k.$ Another interpretation of the above definition is that every graph ...
Jernej's user avatar
  • 3,463
5 votes
1 answer
364 views

Lower bound for diagonal Ramsey numbers —- reference request

Using the first moment method, in 1947 Erd\H{o}s gave a lower bound on the diagonal Ramsey numbers $R(k,k)$: $$ R(k,k) \geq (1+o(1))\frac{k}{e\sqrt{2}} 2^{k/2}. $$ In 1975 Spenser used the Lov\’asz ...
David Galvin's user avatar
  • 1,112
4 votes
2 answers
229 views

Colouring Positive Integers

Does anyone know any reference or proof for the following problem? Let $m$ and $n$ be positive integers, $m,n \geq 2$. Each positive integer is coloured in one of $m$ different colours. Is it ...
jack's user avatar
  • 3,153
4 votes
1 answer
211 views

Another funny kind of Ramsey number

Definition. $h(n_1,n_2)$ is the least number $m$ such that, if the edges of $K_m$ are colored with two colors, $1$ and $2,$ then for some color $i\in\{1,2\}$ there is a set $W\subseteq V(K_m)$ such ...
bof's user avatar
  • 13.4k
4 votes
1 answer
175 views

Partition Calculus and Ramsey theory question

These topics are outside of my area of research, so I am not quite sure where in the literature to find the answers. In what follows, if $X$ is partially ordered and $n$ is a natural number, let $[[...
user-1's user avatar
  • 43
4 votes
0 answers
224 views

A probabilistic proof of van der Waerden theorem

Is there an elementary proof of van der Waerden's theorem on arithmetic progressions using probabilistic methods?
Mohammad Golshani's user avatar
4 votes
0 answers
136 views

An upper bound on diagonal k-colored Ramsey number

I need a reference on any upper bound on $R(n, n, \dots, n)$ with $k$ arguments. For example, the standard recurrent bound gives something like $k^{kn}$, but I cannot find any written explicit bound.
JIOCb's user avatar
  • 41
3 votes
1 answer
196 views

Multipartite Ramsey theorem

Given $c<\infty$ colors, positive integers $k_1,\dots,k_n$ and positive integers $N_1,\dots,N_n$. Then there exist positive integers $M_1,\dots,M_n$ so that for disjoint finite sets $A_1,\dots,A_n$ ...
Fedor Petrov's user avatar
2 votes
1 answer
763 views

Geometric van der waerden theorem

Van der Waerden theorem states that sufficiently long initial segment of the natural numbers when divided into $r$ parts contains an arithmetic progression of length $k$. The length of the initial ...
user avatar
1 vote
1 answer
208 views

Infinite Ramsey theorem for strings (instead of sets)?

The infinite Ramsey theorem implies that, if we color the $n$-element subsets of $N:=\{0,1,2,\ldots\}$ in a finite number of colors, then there will exist an infinite subset $A\subseteq N$ such that ...
Stasys's user avatar
  • 113
0 votes
1 answer
78 views

References for properties which are invariant under partition of $\mathbb{Z}$ by a finite number of sets

A well known result in Ramsey theory is: If the set of positive integers is partitioned into a finite number of sets, then at least one of these sets will contain a solution to $x+y=z$ By "...
proofromthebook's user avatar
0 votes
1 answer
142 views

Left syndeticity and right syndeticity in nilpotent group

$\DeclareMathOperator\Pf{\mathcal{P}_\mathrm{f}}$Question: Does there exist any reference regarding the study of left and right syndeticity in nilpotent group? More specifically, did anyone introduce/...
Surajit's user avatar
  • 73
0 votes
0 answers
86 views

Real world application of large sets like syndetic sets, central sets

Large sets in $\mathbb{N}$ have strong combinatorial structures. For example, it is known that central sets in $\mathbb{N}$ contain arbitrarily long arithmetic progressions. It also contains solutions ...
Arpita Ghosh's user avatar