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

**10**

votes

**1**answer

331 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

104 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

312 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

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

**6**

votes

**0**answers

180 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

54 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

49 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

217 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

95 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

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

**3**

votes

**0**answers

94 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

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

**5**

votes

**0**answers

233 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

189 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

68 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

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

**15**

votes

**0**answers

371 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

880 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

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

**4**

votes

**2**answers

174 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

99 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

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

**16**

votes

**0**answers

495 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

162 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

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

**5**

votes

**0**answers

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

**7**

votes

**0**answers

458 views

### Ramsey number conjectures?

It's well known that R(r, s) ≤ R(r − 1, s) + R(r, s − 1).
I believe that there should be some formulas between these three numbers above and R(r - 1, s - 1).
After observing the latest datas ...

**4**

votes

**1**answer

111 views

### Finding a monochromatic cycle in clique

1) what is the minimum $n$ such that in every $2$ - coloring of $K_n$ there exist a monochromatic copy of $C_m$ ?
2) moreover, what is the minimum $n$ such that in every $r$ - coloring of $K_n$ there ...

**8**

votes

**0**answers

94 views

### Stable Acute Triangles in a Grid

The following combinatorial question came up while trying to prove a lemma for my research. Let $[N]$ denote the $N\times N$ grid inside the integer lattice $\mathbb{Z}\times\mathbb{Z}.$ The square ...

**4**

votes

**0**answers

87 views

### An upper bound on diagonal k-colored Ramsey number

I need a reference on any upper bound on $R(n, n, \dots, n)$ with $k$ arguments.
For example, the standard recurrent bound gives something like $k^{kn}$, but I cannot find any written explicit bound.

**6**

votes

**1**answer

224 views

### Ramsey type theorems and Magidor's forcing

Consider Prikry's forcing for changing the cofinality of a measurable cardinal into $\omega.$ The forcing has the Prikry property and one can prove this either directly or using Rowbottom's theorem ...

**8**

votes

**1**answer

302 views

### What is the upper bound of $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$ times}$?

Just some context: $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$ times}\leq n$, means that any colouring of a complete graph, $k_n$, on $n$ vertices or more with $k$ colours must contain a monochromatic ...

**4**

votes

**0**answers

430 views

### Bounding Ramsey numbers with quadratic or higher residues

For parameters $m,k$, we call a graph on $n$ vertices Ramsey if it contains no complete subgraph on $m$ vertices and its complement contains no complete subgraph on $k$ vertices (or vice versa). The ...

**0**

votes

**0**answers

143 views

### A Non-trivial intersecting set system problem

Liven large enough $k\in\Bbb N$ fix $m\in\{2,3,\dots,k\}$ and fix $4k$ cardinality set $K_{4k}$.
What is the maximum $n\in\Bbb N$ such that at some $t\geq2n-1$ there are $$\mbox{ subsets }L_1,L_2,\...

**1**

vote

**1**answer

136 views

### Infinite Ramsey theorem for strings (instead of sets)?

The infinite Ramsey theorem implies that, if we color the $n$-element subsets of $N:=\{0,1,2,\ldots\}$ in a finite number of colors, then there will exist an infinite subset $A\subseteq N$ such that ...

**12**

votes

**1**answer

365 views

### Ramsey Theorem for the class ORD

Is it true that given a (definable) 2-coloring of the ORD (class of ordinals), $\chi:[ORD]^{2}\rightarrow\lbrace 0,1\rbrace$, there exists an unbounded $H\subseteq ORD$ which is homogenous, i.e., $\...

**5**

votes

**1**answer

199 views

### A variant of Ramsey numbers

The well known Ramsey number $R(k)$ is the least integer $n$ so that every 2-edge coloring of $K_n$ contains a monochromatic $K_k.$
Another interpretation of the above definition is that every graph ...

**10**

votes

**3**answers

318 views

### How many colors do we need to avoid bichromatic triangles?

Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors.
I wonder if the following type of question has ...

**3**

votes

**1**answer

394 views

### Uniqueness of Ramsey counter-examples

I asked this question a while ago on math exchange with no satisfying answer, so I thought I'd try my luck here, if the question doesn't fit the site please close it or let me know and I'll close it.
...

**5**

votes

**0**answers

156 views

### For which Ramsey type results density versions are wrong?

I look for examples of Ramsey-type statements, for which the density counterparts do not hold.
Example: usual Ramsey theorem. If all edges of a complete graph $K_n$ are colored in $c$ colors, there ...

**3**

votes

**1**answer

188 views

### Lower bound construction for Multidimensional Szemerédi's Theorem

The Multidimensional version of Szemerédi's theorem given by Theorem 10.2 in Tim Gower's paper from 2007 has the following statement.
Let $\delta>0$ and $k\in\mathbb{N}$. Then if $N$ is ...

**38**

votes

**2**answers

4k views

### Why is this new result such a big deal?

This popular article reports a recent result in reverse mathematics, showing that a certain theorem in Ramsey theory is provable from RCA$_0$, the base theory in SOSOA. Then there are a bunch of ...

**3**

votes

**1**answer

222 views

### An extremal combinatorics problem involving column summation

Given $n\in\Bbb N$, $\alpha>0$, $\beta\in\big[\frac12,1\big]$ denote $\mathcal R_{n,\alpha,\beta}$ as collection of all $2^n\times 2^{n^\alpha}$ $0/1$ matrices with every row summing to strictly ...

**1**

vote

**2**answers

158 views

### question about literature in the field of Ramsey's theory [closed]

i am searching for an on- line paper or a book, or maybe just a paper or a book which consists a proof of finite Ramsey's theorem for sets (not for graphs). i need a combinatorial proof which is not ...

**7**

votes

**1**answer

298 views

### The Hales-Jewett Theorem for an infinite alphabet

Recall the Hales-Jewett Theorem:
HJT: Given a finite alphabet $A$ and some $r \in \mathbb{N}$, there is some $H \in \mathbb{N}$ such that whenever $A^H$, the set of all length-$H$ words from $A$, ...

**8**

votes

**0**answers

179 views

### Is there a Ramsey theory for Kneser graphs?

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...

**3**

votes

**2**answers

184 views

### Partition regular systems: do they have solution in (very dense) set of integers?

A partition regular system is a linear system of equations of the form $A\cdot x=0$, which satisfies a Ramsey-type result (namely, that for each $r>0$ whenever we colour the integers in $r$ classes,...

**14**

votes

**1**answer

422 views

### Convergence rate of Fagin's 0-1 law for first-order properties of random graphs

Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the ...

**4**

votes

**1**answer

92 views

### Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors

You are given a multigraph $G$ with $n$ vertices as follows:
$V := (v_1, v_2, \dots ,v_n)$
$C := \{c_1, c_2, \dots\}$, be an infinite set of colors.
$f: V \rightarrow \mathbb{P}_{\le m}(C) $, a ...

**18**

votes

**0**answers

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