All Questions
20 questions
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?
- 32.1k
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 ...
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/...
- 73
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 "...
- 115
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 ...
- 71
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 ...
- 32.1k
5
votes
1
answer
363
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 ...
- 1,112
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 $[[...
- 43
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 ...
- 13.4k
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 ...
- 13.4k
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 ...
- 13.4k
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 ...
- 3,153
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.
- 41
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 ...
- 113
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 ...
- 3,463
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 ...
- 18.8k
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?
user39297
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 ...
user14875
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$ ...
- 109k
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 $\...
- 894