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

Filter by
Sorted by
Tagged with
40
votes
6answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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 ...