# Tagged Questions

**4**

votes

**1**answer

178 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?

**3**

votes

**1**answer

581 views

### Big binary tree as an induced subgraph

I believe this is true:
Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an
induced subgraph which is a subdivision of a large binary tree or the line ...

**2**

votes

**1**answer

179 views

### Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...

**3**

votes

**1**answer

248 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 ...

**3**

votes

**1**answer

102 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$ ...

**7**

votes

**1**answer

313 views

### Combining van der Waerden's theorem with Ramsey's theorem

Consider positive integers $c$, $k$, and $s$. Does there exist some $N = N(c,k,s)$ such that the following holds?
Take any $c$-coloring of the $k$-tuples of integers in $[1,N]$. Then there is an ...

**18**

votes

**1**answer

2k views

### Reconstructing the argument that yields Graham's number

Graham's number achieved a kind of cult status, thanks to Martin Gardner, as the largest finite number appearing in a mathematical proof. (It may no longer hold that record, but that is not my concern ...

**9**

votes

**2**answers

345 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 ...

**2**

votes

**1**answer

172 views

### A Ramsey-like lower bound?

Does there exist a graph $G$ which cannot be properly vertex-coloured with 3 colours (i.e. $G$ has chromatic number at least 4), such that for every graph $H$, if $H$ contains a triangle but there ...

**4**

votes

**0**answers

139 views

### Weak Arithmetic Progressions

I am studying a special type of a sequence on the naturals which I am calling a weak arithmetic progression.
Formally I call a k-sequence $x_1< x_2 \cdots< x_k$ a weak arithmetic progression ...

**3**

votes

**2**answers

659 views

### Hales Jewett Theorem

In the book Ramsey Theory by Graham, Rothschild and Spencer the authors state:
The Hales Jewett Theorem strips van der Waerden's theorem of its unessential elements and reveals the heart of Ramsey ...

**5**

votes

**2**answers

441 views

### The Problem about 2-coloring finite plane

Suppose we color a $X \times X$ finite plane by red and blue arbitrarily. How large does X need to be to guarantee a monochromatic combinatorial square $k \times k$
1 0 1 0 1 1
1 1 1 1 1 1
1 ...

**1**

vote

**1**answer

371 views

### Combinatorial optimization and graph coloring

I am considering the following problem:
(i) Fix $n$ and color the edges of $K_n$ red and blue arbitrarily.
(ii) Let $M$ be the set of monochromatic triangles in $K_n$ and define $g:M\rightarrow ...

**2**

votes

**0**answers

228 views

### Slightly improving bounds on two-color Ramsey numbers by globally pruning edges and counting connected vertices in instances of two-colored complete graphs

The two-color Ramsey number, $R(m, n)$, is the minimum number of vertices, $||V||$, in a complete graph necessary for there to exist a clique of order $m$ or an independent set of order $n$. In terms ...

**10**

votes

**3**answers

723 views

### Density Ramsey theorems with explicit asymptotics

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there?
I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem.
...

**6**

votes

**3**answers

705 views

### Is this Ramsey-type problem an open problem?

A blog claims that the following Ramsey-type (or van der Waerden type) problem is open:
If the natural numbers are colored with finitely many colors, must there exist x and y (not both 2) such that ...

**3**

votes

**0**answers

197 views

### Constructive lower bounds for multicolor Ramsey numbers

The $k$-color Ramsey number of the complete graph $K_n$, denoted with $R_k(n)$, is defined to be the smallest integer $t$, such that in any $k$-coloring of the edges of $K_t$, there is a complete ...

**3**

votes

**0**answers

103 views

### Bound on how many 2-colored graphs have maxredclique $i$, maxblueclique $j$

Fix $i,j$. I want a bound $F(i,j)$ on the following:
$\sum_{n=1}^\infty$ (the number of 2-colorings of the edges of $K_n$ such that
the MAX RED clique is size exactly ...

**3**

votes

**1**answer

368 views

### Permutations of Grid Colorings

Hello all,
This question arises out of a Ramsey-theoretic study related (but tangential) to this question on CSTheory: Grid $k$-coloring without monochromatic rectangles.
Background:
In general, we ...

**2**

votes

**3**answers

604 views

### Arithmetic progressions of length 3 in subset of Z_n of size n^d

Let $A\subset\mathbb{Z}/n\mathbb{Z}$ such that: $|A|>n^{d}$ ($0< d <1$).
Let $C=\{(x,y,2y-x)\in A\times A \times A\}$ be the set of $3$-term arithmetic progressions within $A$.
[The ...

**22**

votes

**3**answers

1k views

### Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...

**4**

votes

**1**answer

542 views

### Best lower bound for off-diagonal Ramsey numbers

What are the current best lower bounds for off-diagonal Ramsey numbers $R(k,l)$ with $l$ of order unity and asking for asymptotic behavior for large $k$, such as $R(k,4)$, $R(k,5)$, and so on? ...

**13**

votes

**3**answers

724 views

### Differences of near diagonal Ramsey numbers.

I am a graduate student trying to get involved in Ramsey theory. My question comes from:
Erdős on graphs: his legacy of unsolved problems
By Fan R. K. Chung, Paul Erdős, Ronald L. Graham
p.14 of ...

**8**

votes

**1**answer

452 views

### monochromatic cycle-free colouring of the complete graph on R?

Hi
So there is an edge-colouring of a complete graph on R (the reals), with countably many colours that as no monochromatic triangle. To find it map R to (0,1) write the numbers in binary and if 2 ...

**2**

votes

**2**answers

1k views

### Proofs of Lower Bounds for Ramsey Numbers?

As a sort of dual question to this question, I am wondering what proofs people know of lower bounds on Ramsey numbers $R(k, k)$. I know of two proofs: there is Erdos's beautiful probabilistic ...

**9**

votes

**2**answers

1k views

### Noncombinatorial proofs of Ramsey's Theorem?

I know of 2(.5) proofs of Ramsey's theorem, which states (in its simplest form) that for all $k, l\in \mathbb{N}$ there exists an integer $R(k, l)$ with the following property: for any $n>R(k, l)$, ...

**17**

votes

**2**answers

696 views

### Ramsey multiplicity

Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ ...

**5**

votes

**2**answers

245 views

### Bounds on a partition theorem with ambivalent colors

I've been running into the following type of partition problem.
Given positive integers h, r, k, and a real number ε ∈ (0,1), find n such that if every (unordered) r-tuple from an n ...

**21**

votes

**5**answers

4k views

### Erdos Conjecture on arithmetic progressions

Introduction:
Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.
Question:
I ...

**15**

votes

**10**answers

2k views

### Applications of infinite Ramsey's Theorem (on N)?

Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) ...

**5**

votes

**5**answers

949 views

### Bound on cardinality of a union

Suppose I have n finite sets A1 through An contained in some fixed set S, and I am given non-negative integers N and N1 through Nn such that each Ai has cardinality N, and each k-tuple intersection ...

**8**

votes

**5**answers

933 views

### Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number R(k). Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...