# Questions tagged [ramsey-theory]

Branch of combinatorics with the philosophy that 'total disorder is impossible'. For example, Ramsey's theorem asserts that for each $n$, every sufficiently large graph either contains a clique of size $n$ or a stable set of size $n$.

154
questions

**40**

votes

**6**answers

3k views

### Ron L. Graham’s lesser known significant contributions

Ron L. Graham is sadly no longer with us.
He was very prolific and his work spanned many areas of mathematics including graph theory, computational geometry, Ramsey theory, and quasi-randomness. His ...

**5**

votes

**1**answer

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

**6**

votes

**1**answer

102 views

### Ramsey theory in infinite-dimensional projective spaces

Let $\mathbb{F}_q$ be a finite field and $k$ be a positive integer. If we colour each point of the infinite-dimensional projective space $\mathbb{F}_q \mathbb{P}^{\infty}$ with one of $k$ colours, can ...

**2**

votes

**1**answer

116 views

### Additivity of the upper Banach density

The following notion of upper Banach density was defined (Definition 2.1(c)) by Hindman and Strauss in their paper 'Density in arbitrary semigroups':
Definition: Let $S$ be a semigroup, let $\mathcal{...

**0**

votes

**1**answer

81 views

### Ramsey graph for C4 graph

Does there exist a ramsey graph of C4 such that an induced subgraph has a monochromatic C4, no matter how the edges are colored?

**7**

votes

**1**answer

145 views

### 3 term van der Waerden with large step size

Let $P(n)$ be the statement "any $n$ coloring of $\mathbb{N}$ contains a monochromatic progression $a, a+d, a+2d$ such that $d>a$".
For which $n$ is $P(n)$ true?
It's easy to see that $P(2)$ is ...

**-7**

votes

**1**answer

336 views

### Is Green-Tao's theorem a consequence of Van der Waerden theorem?

Wanting to learn a bit about Ramsey's theory, I read the corresponding article on Wikipedia and stumbled upon this:
"Le théorème de van der Waerden[2] : pour tous entiers c et n, il existe un entier[...

**5**

votes

**0**answers

186 views

### Ramsey-Kuratowski numbers

A simple graph is an ordered pair of sets $\,\Gamma:=(V\,E)\,$ such that
$\,E\subseteq\binom V2.\ $ Kuratowski graph of the first kind is
$\,K_n:=\left(V\,\,\binom V2\right),\,$ where $\,n:=|V|.\,$ ...

**0**

votes

**0**answers

47 views

### Counting progressions for Ramsey-type number

I'm currently learning about Ramsey theory and how to use the probabilistic method to find lower bounds. Currently I'm looking at a family, which I'll call $H$, that is composed of the following ...

**2**

votes

**1**answer

83 views

### Ramsey type properties of $F_\sigma$ ideals

Let $I \subseteq 2^\omega$ be any $F_\sigma$ ideal containing every finite sets :
$\forall X \in I\ \forall Y \subseteq X\ \text{ we have } Y \in I$
$\forall k\ \forall X_1,\dots,X_k \in I\ X_1 \cup \...

**2**

votes

**0**answers

211 views

### Is there a known proof that $R(5,5)\leq 47$ in Ramsey theory?

As an application to a model describing graphs with partial information, I found what might be an (as yet unverified) proof that $R(5,5)\leq 47$.
According to the Dynamic Survey of Ramsey Numbers at ...

**20**

votes

**1**answer

501 views

### If $S_\mathbb N$ is partitioned into finitely many pieces, must one piece contain a “skew copy” of every countable group?

Suppose $G$ and $H$ are groups. $C \subseteq H$ is called a skew copy of $G$ in $H$ if $C = hK$ for some $h \in H$ and some subgroup $K$ of $H$ with $K \cong G$.
Question 1: Suppose the infinite ...

**1**

vote

**0**answers

145 views

### Winning strategies for a game on the natural numbers

Define $$F=\{(l_n, k_n)_{n=1}^t: t,l_n, k_n \in \mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}.$$ Suppose that I have a collection $G\subset F$, which is a set of ''good'' sequences.
...

**2**

votes

**0**answers

154 views

### An analytic game and Ramsey's theorem

Let $$P=\{(l_n, m_n)_{n=1}^t: l_n, m_n,t\in\mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}$$ and suppose that $T$ is some subset of $P$. Suppose that $T$ also has the following properties: ...

**0**

votes

**1**answer

173 views

### Games and Ramsey's theorem

Here, we identify subsets of $\mathbb{N}$ with sequences obtained by listing the members of the set in strictly increasing order. Suppose that we have some set $\mathcal{F}$ of sets (sequences) of the ...

**3**

votes

**0**answers

170 views

### Consistency of a tighter bound than given by Erdős–Rado in a special case

Let $0 < n, \ell$ be natural numbers with $n < \ell$. We will define a function $F_{n\ell}(\kappa)$ on infinite cardinals indexed by $n$ and $\ell$.
To compute $F_{n\ell}(\kappa)$ let $A$ be a ...

**1**

vote

**0**answers

121 views

### Kastanas' game and completely Ramsey sets [closed]

Recently I was reading the article ''On the Ramsey property for sets of reals'' of Ilias Kastanas (https://www.jstor.org/stable/2273667?seq=1#metadata_info_tab_contents), in this article the author ...

**2**

votes

**0**answers

94 views

### Coloring triples in trees

Definitions
Let us say a tree is a partially ordered set $(P, \leqslant )$ such that for any $t\in P$, the ancestor set $\{s\in P: s\leqslant t\}$ is finite and linearly ordered. We let $MAX(P)$ ...

**5**

votes

**0**answers

61 views

### Consequences of Ramsey-numbers of hypergraphs

We know that the (2-color) Ramsey-numbers for $3$-uniform hypergraphs are between roughly $2^{n^2}$ and $2^{2^n}$, and the situation is similar to $k$-uniform hypergraphs for every $k\ge 3$. (A recent ...

**1**

vote

**0**answers

101 views

### Is the Upper Banach density always zero with respect to some sequence of Finite subset

The following question came to me while reading the paper 'Density in Arbitrary Semigroups' by Hindman and Strauss.
Question: Given an infinite subset $A$ of $\mathbb{N}$ such that $A^c$ is also ...

**8**

votes

**0**answers

209 views

### Metrically Ramsey ultrafilters

On Thuesday I was in Kyiv and discussed with Igor Protasov the system of MathOverflow and its power in answering mathematical problems. After this discussion Igor Protasov suggested to ask on MO the ...

**1**

vote

**0**answers

108 views

### Induction on the number of edges $(-1)^wI(G)\leq (-1)^w\sum_{i=0}^w(-1)^ig_i.$

I need help with this theorem about graph theory. In Some Graph Theoretic Results Associated with Ramsey's Theorem of Graver and Yackel find this proposition 5.
Proposition 5: Let $G$ be a graph with ...

**5**

votes

**1**answer

120 views

### Does every bijective graph endomorphism restrict to a full-cardinality isomorphism?

Given a graph $G$, and a bijective endomorphism $f$ (that is, a graph homeomorphism $f : G \to G$ that establishes a bijection on the vertices), it is true that $f$ is an automorphism whenever $|G|$ ...

**4**

votes

**1**answer

137 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 $[[...

**10**

votes

**1**answer

388 views

### Looking for “Set theory for a small universe” by Ketonen

In the paper Partition theorems for systems of finite subsets of integers, Pudlák and Rödl show a Ramsey-type result. The main feature of this result is that the sizes of sets in such systems are not ...

**4**

votes

**0**answers

132 views

### The set of homogeneous solutions of a clopen contains an hyperarithmetical set

In the context of Galvin-Prikry generalization of Ramsey's theorem, I read in a couple of papers ([1],[2]) that Solovay [3] proved that if $P$ is a clopen of $[\mathbb{N}]^{\mathbb{N}}$ then the set ...

**8**

votes

**1**answer

327 views

### A combinatorial property of uncountable groups, II

Problem 1. Is it true that each uncountable group $G$ contains two subsets $A,B\subset G$ such that
1) for any $x,y\in G$ the intersection $xA\cap yB$ is finite and
2) for any function $\...

**6**

votes

**1**answer

222 views

### A combinatorial property of uncountable groups

Let $A,B$ be two uncountable sets in a group $G$ such that for any elements $x,y\in G$ the intersection $xA\cap yB$ is finite. Let $\Phi:G\to 2^G$ be a function assigning to each element $x\in G$ some ...

**7**

votes

**0**answers

397 views

### $R(3,6) = 18$, especially proving that $R(3,6)>17$

I'm studying the Ramsey numbers, especially $R(3,6) = 18$
I understand that the proof using the theorem $R(m,n) <R(m-1,n)+R(m,n-1)$ can only prove that $R(3,6)<20$. However by Cariolaro's "On ...

**1**

vote

**1**answer

56 views

### monochromatic induced subgraph in a complete 3-partite graph

$H=(V_1\cup V_2 \cup V_3, E)$ is a complete $3$ partite graph such that $|V_1|=|V_2|=|V_3|=n$ . Color the edges with three colors.
My question is: Is it possible to find sets $V_1' \subset V_1, V_2' ...

**1**

vote

**0**answers

65 views

### Equivalent condition for Poincare polynomial

I have found a statement in the introduction of the paper 'Sets of Recurrence and Generalized Polynomials' by Bergelson & Haland, which is
Result: Given a polynomial $p \in \mathbb{R}[x]$ such ...

**2**

votes

**0**answers

280 views

### Proof of Hales-Jewett Theorem

I was studying the paper 'Set-polynomials and polynomial extension of the Hales-Jewett Theorem' by Bergelson & Leibman, and I'm having problem with the proof of 'Proposition L', which is (for the ...

**3**

votes

**1**answer

110 views

### Partition theorems for located words

In this paper Bergelson, Blass, and Hindman prove the following
Theorem 1.2 Let $W(\Sigma; v)$ be colored with finitely may colors and let $\bar s$ be an infinite sequence from $W(\Sigma; v)$. ...

**4**

votes

**1**answer

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

**4**

votes

**0**answers

106 views

### Selectors for bases of ultrafilters

If $\mathcal{U}$ is a selective (Ramsey) ultrafilter on $\omega$ and $\mathcal{B}$ is its base, then for every sequence $A_0\supsetneq A_1\supsetneq A_2\supsetneq\ldots$ in $\mathcal{B}$ there exists $...

**6**

votes

**0**answers

98 views

### What is the smallest number of vertices in a graph whose every orientation contains a directed straight path of length 3

For a graph $\Gamma$ and a digraph $\vec H$ we write $\Gamma\Rightarrow \vec H$ if any orientation of $\Gamma$ contains an isometric and isomorphic copy of the digraph $\vec H$. Since each graph ...

**17**

votes

**0**answers

882 views

### Almost monochromatic point sets

There are many sort of equivalent theorems about monochromatic configurations in finite colorings, such as Van der Waerden, Hales-Jewett or Gallai's theorem, the latter of which states that in a ...

**7**

votes

**0**answers

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

**1**

vote

**0**answers

72 views

### Appearance of “Fat Spiders” in Graphs

When investigating the properties of least detours of edges in complete, weighted graphs, I noticed an interesting phenomenon in the visualization of graphs where the nodes correspond to points in the ...

**3**

votes

**2**answers

244 views

### A direct proof that every $r$-colored complete graph on $n=(r+1)m-(r-1)$ vertices has a monochromatic matching of size $m$?

Cockayne and Lorimer ("The Ramsey number for stripes" 1975) prove that in every $r$-colored complete graph on $n=\sum_{i=1}^rm_i+m_1-(r-1)$ vertices, where $m_1\geq \dots\geq m_r\geq 1$, has a ...

**22**

votes

**1**answer

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

**15**

votes

**1**answer

1k views

### Ramsey Number R(3,3,4)

How much is known about the Ramsey number R(3,3,4)? There is a trivial upper bound of 34, but are any tighter bounds known?

**19**

votes

**1**answer

729 views

### On Erdos-Kakutani like Equivalents of the Failure of Continuum Hypothesis

Among all mysterious equivalents of the Continuum Hypothesis and its negation, there is an algebraic combinatorial equivalent of the $\neg CH$ by Erdos and Kakutani (MR0008136) as follows:
Definition. ...

**4**

votes

**2**answers

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

**4**

votes

**0**answers

107 views

### Set version of ramsey type problem

For two sets of numbers $A,B$, write $A<B$ iff $\max A<\min B$.
For a sequence of integers $a_0,\cdots,a_{n-1}>0$,
let $Prop(a_0,\cdots,a_{n-1})$ denote the following proposition:
Given $n$ ...

**6**

votes

**1**answer

325 views

### Ramsey type theorem

Let $\mathcal{P}(\{0,\dotsc,7\})$ denote the power set of $\{0,\dotsc,7\}$.
Is the following true?
For any function $f: \mathcal{P}(\{0,\dotsc,7\})\rightarrow\{0,1\}$ there exists $0\leq k\leq 3$ ...

**17**

votes

**0**answers

606 views

### Ramsey's theorem for the first uncountable ordinal

Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...

**3**

votes

**1**answer

174 views

### How many sums vs products are there?

Motivated by applications of Ramsey theory, Schur's theorem states that for any partition of the positive integers into a finite number of parts, one of the parts contains three integers $x, y, z$ ...

**3**

votes

**0**answers

106 views

### Maximizing a subset of the binary vector space such that no sum of four distinct elements is zero

I have researched a problem for about 2 years, and I want to know if there exists any previous results (I can't seem to find any). The problem goes:
What is the largest subset of a $2k$-dimensional ...

**6**

votes

**1**answer

98 views

### Containment of minimal 2-Ramsey-graphs in minimal 3-Ramsey-graphs

Let $G$ be a minimal $2$-colour Ramsey-graph for $H$.
Must there exist a minimal $3$-colour Ramsey-graph $F$ for $H$ with $G\subset F$?
I am wondering if anything is known about this, particularly ...