The ramsey-theory tag has no wiki summary.

**2**

votes

**0**answers

49 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

63 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

936 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

317 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

534 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

184 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

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

**25**

votes

**0**answers

621 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

157 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

47 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

367 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

689 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

395 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

81 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

853 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

513 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

386 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

55 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

209 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

609 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

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

**2**

votes

**1**answer

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

**4**

votes

**2**answers

175 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

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

vote

**1**answer

113 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

497 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

193 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

234 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

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

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

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

754 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

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

**5**

votes

**1**answer

171 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

186 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

193 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

799 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

181 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

512 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

394 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

253 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

322 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

386 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

773 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

792 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

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