Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
2answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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 ...