The ramsey-theory tag has no usage guidance.

**16**

votes

**0**answers

250 views

### Simpler proofs of certain Ramsey numbers

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture.
But for bigger Ramsey ...

**2**

votes

**0**answers

63 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...

**0**

votes

**0**answers

79 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...

**10**

votes

**6**answers

1k views

### Algorithms for calculating R(5,5) and R(6,6)

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:
Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...

**3**

votes

**1**answer

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

**10**

votes

**2**answers

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

**2**

votes

**0**answers

217 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)$?
...

**6**

votes

**2**answers

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

**27**

votes

**0**answers

666 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

**0**answers

162 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

48 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

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

**11**

votes

**2**answers

711 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

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

**6**

votes

**0**answers

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

**8**

votes

**3**answers

879 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

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

**5**

votes

**1**answer

392 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$,
$$
...

**2**

votes

**0**answers

56 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

103 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

230 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

612 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

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

**2**

votes

**1**answer

306 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

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

**4**

votes

**2**answers

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

**7**

votes

**2**answers

483 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

153 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**

vote

**1**answer

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

**7**

votes

**2**answers

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

**-1**

votes

**1**answer

195 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

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

**8**

votes

**3**answers

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

**20**

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

**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

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

**5**

votes

**1**answer

467 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,Ⅲ. ...

**7**

votes

**1**answer

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

**2**

votes

**1**answer

194 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

151 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

197 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

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

**4**

votes

**1**answer

183 views

### Large bicliques in r-partite graphs containing no independent sets having one vertex from each class

Let $G$ be a multipartite graph on $r$ classes, each containing $k$ vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a ...

**5**

votes

**2**answers

516 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

423 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

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

**7**

votes

**3**answers

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

**1**

vote

**2**answers

389 views

### Quasi-Ramsey Graphs

A graph with number of vertices less than R(n,n)-1, is called quasi-Ramsey of case n, if it has no complete graph Kn in itself or its complementary graph, and if added another vertex, no matter how it ...

**10**

votes

**3**answers

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

**7**

votes

**3**answers

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