The ramsey-theory tag has no wiki summary.

**10**

votes

**2**answers

500 views

### Does van der Waerden's Theorem hold for $\omega_1$?

One way to phrase van der Waerden's Theorem is:
For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...

**3**

votes

**1**answer

309 views

### Is this version of van der Waerden's Theorem consistent with ZFC?

One way to phrase van der Waerden's Theorem is:
For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...

**11**

votes

**2**answers

600 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

**0**answers

164 views

### What is the complexity of determining Ramsey Number?

In the notation of Garey and Johnson [1], two problems related to Ramsey Problem were defined:
$\textbf{ARROWING}$
Instance: (Finite) graphs $F$, $G$ and $H$.
Question: Does $F\rightarrow (G, H)$?
...

**25**

votes

**0**answers

582 views

### 3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.
Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...

**6**

votes

**2**answers

105 views

### Reference request: monochromatic paths in edge-colored complete graphs

Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$.
...

**6**

votes

**0**answers

152 views

### A generalization of SOCA

Roughly speaking, SOCA (Semi Open Coloring Axiom) says that for an open coloring of the unordered pairs over an uncountable separable metric space you can always find an uncountable homogeneous subset ...

**1**

vote

**0**answers

46 views

### Genus tradeoffs in bipartite graph

Given $G$ as bipartite graph of genus $g(G)$ with number of vertices of each color being $N$ with $A$ as $N\times N$ biadjacency matrix. Denote $\bar{G}$ to bipartite graph of genus $g(\bar{G})$ of ...

**11**

votes

**3**answers

363 views

### Sets of points containing permutations - a Ramsey-type question

The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with ...

**5**

votes

**1**answer

169 views

### Sparse ramsey theory

It is known that for any graph H and all $k∈N$, there exists a graph $G$ such that any $k$-coloring of the edges of $G$ yields a monochromatic copy of H and ω(G)=ω(H) (the two graphs have the same ...

**17**

votes

**3**answers

558 views

### Ergodic limits along subsets of $\mathbb{N}.$

Let say that an infinite subsets $A$ of $\mathbb{N}$ is "nice w.r.to ergodic limits", if it can replace $\mathbb{N}$ in the individual ergodic theorem, that is, if it is such that the following ...

**11**

votes

**2**answers

676 views

### Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper?

This may be inappropriate for MO, but here goes: if I have understood the statement of the Erdős–Rado theorem correctly, then it contains as a special case the following result:
if $\mu$ is ...

**9**

votes

**1**answer

368 views

### Could there be an exact formula for the Ramsey numbers?

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$.
Is it possible that there ...

**12**

votes

**2**answers

2k 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)$, ...

**6**

votes

**0**answers

80 views

### Why have most maximal cliques of Paley graphs odd size?

I ask this question mainly by curiosity.
See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$.
Is there an ...

**7**

votes

**3**answers

840 views

### A stronger version of Van der Waerden's theorem?

Let $W$ be an infinite word over a finite alphabet $\{1,\dots,n\}$ and $k$ a positive integer. An easy application of Van der Waerden's theorem implies the existence of $k$ disjoint and consecutive ...

**10**

votes

**2**answers

511 views

### Is every knot unavoidable in the embeddings of some graph?

Is it the case that, for any given knot $K$,
there exists some graph $G$ whose every embedding into $\mathbb{R}^3$
(or into $\mathbb{S}^3$)
contains a cycle that realizes $K$?
I know the ...

**30**

votes

**4**answers

2k 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 ...

**7**

votes

**2**answers

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

**5**

votes

**1**answer

383 views

### Are semigroups with finite-to-one right multiplication “moving”?

A semigroup $S$ is moving if $S$ is infinite, and for all finite
$F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that,
for all but finitely many $s\in S$,
$$
...

**3**

votes

**1**answer

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

**4**

votes

**2**answers

170 views

### Is There a Graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free

Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nesetril and Rodl proved that for a graph $G$, there exists a graph $F\to G$ with ...

**2**

votes

**0**answers

53 views

### Moving from positive upper Banach density to positive upper density [closed]

Under which conditions positive upper Banach density implies positive upper or lower asymptotic density? Thanks a lot.

**1**

vote

**0**answers

101 views

### Mixed Tsirelson Norm

A couple of days ago I posted this question on Mathematics Stack Exchange. Surprisingly, so far, I haven't received any answers or comments about it (besides my own possible answer). Maybe I can get ...

**4**

votes

**1**answer

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

**12**

votes

**6**answers

16k views

### Magnitude of Graham's Number?

I recently stumbled across this number, and then (foolishly, most likely) decided to try to describe it in a blog post
http://frothygirlz.com/2010/01/14/big-numbers-part-2/
Q - Are there any ...

**2**

votes

**1**answer

193 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 , ...

**15**

votes

**10**answers

3k 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

**2**answers

687 views

### Infinite Ramsey theorem with infinitely many colours

Clearly, it is possible to colour the edges of an infinite complete graph so that it does not contain any infinite monochromatic complete subgraph. Now what about the following?
Let $G$ be the ...

**2**

votes

**1**answer

290 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

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

**1**

vote

**1**answer

108 views

### Distribution of Induced Subgraphs of Extremal Ramsey Graphs

Choose $k$. Let $G = (V,E)$ be a graph on $n = R(k,k)-1$ vertices (that is, $G$ is an extremal example for $R(k,k)$, and $g : E \to \{r, b\}$ be an edge 2-coloring such that there is no monochromatic ...

**8**

votes

**3**answers

903 views

### A General Framework for Ramsey Theory ?

There are few results in modern mathematics that I find so deep and full of philosophical implications as Ramsey's theorem.
I am aware (at some basic level) that it has generated a plethora of ...

**7**

votes

**3**answers

319 views

### Extracting countable chains from linear orders

There is a well-known fact in infinite combinatorics asserting that for each infinite linear order $P$ there is a countable subset $R\subseteq P$ of order type either $\omega$ or $\omega^{*}$
(by ...

**7**

votes

**2**answers

459 views

### Deriving Konig's Lemma directly from Infinite Ramsey's Theorem for triples

Let KL denote König's Lemma (for trees over $\mathbb{N}$), and RT(3) denote the
Infinite Ramsey Theorem for triples over $\mathbb{N}$ (notation as in Simpson's
book Subsystems of second order ...

**1**

vote

**1**answer

144 views

### Ramsey numbers and graph spectra

I am interested in graph Ramsey theory. Are there any papers which investigate Ramsey numbers $R(G,G)$ of an arbitrary graph by analyzing the spectrum of $G$? In general, has anyone found any ...

**-1**

votes

**1**answer

190 views

### What is a Ramsey Graph? [closed]

Can anyone explain me what is a Ramsey Graph with a simple example?
What are its properties?

**1**

vote

**1**answer

233 views

### Van der Waerden's Theorem Over $\mathbb{Z}_p$

Define a length $k$ arithmetic progression in $\mathbb{Z}_p$ to be a set of the form
$\{ax+b : x \in [k]\}$ with $a \in \mathbb{Z}_p^*$ and $b \in \mathbb{Z}_p$.
Let $HJ(k, c)$ be the Hales-Jewett ...

**19**

votes

**1**answer

3k 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 ...

**5**

votes

**1**answer

746 views

### Graham-Rothschild via Hales-Jewett

I am currently reading the recent preprint of Dodos, Kanellopoulos, Tyros, where the ambitiously short proof of Density Hales Jewett theorem is provided. The important ingredient is Graham-Rothschild ...

**10**

votes

**3**answers

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

**9**

votes

**2**answers

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

**5**

votes

**1**answer

443 views

### small Ramsey number and Brooks' Theorem

I'm studying about Graph Ramsey Theory now. Starting this study, I'm reading Chvatal and Harary's series of papers. In the second paper (V.Chvatal, F.Harary, Generalized ramsey theory for graphs,Ⅲ. ...

**2**

votes

**1**answer

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

**3**

votes

**0**answers

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

**4**

votes

**0**answers

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

**5**

votes

**0**answers

192 views

### Van der Waerden like theorem

I am trying to develop bounds for the function B(k) where B(k) is defined as the least such positive integer so that whenever the set $\{1,2,\cdots B(k)\}$ is partitioned into two parts at least one ...

**3**

votes

**2**answers

782 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

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

**22**

votes

**5**answers

5k 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 ...