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]

Use for questions in Ramsey Theory, i.e. regarding how large a structure must be before it is guaranteed to have a certain property. Please be especially careful not to ask open questions in this tag.

3
votes
1answer
71 views

Bound of Ramsey number

I'm trying to prove that $5^{k/2}\leq R_{k}(3)=min\{n\in\mathbb{N}, \forall c:e(K_{n})\to [k], \exists ab, bc, ca\in e(K_{n}) \wedge c(ab)=c(bc)=c(ac)\} $ My first attempt was to induction: If it's ...
1
vote
2answers
41 views

Splitting the natural numbers into sets $A$ and $B$ such that for distinct elements $m,n\in A$ we have $m+n\in B$ and vice-versa.

Why it is impossible to split the natural numbers into sets $A$ and $B$ such that for distinct elements $m, n \in A$ we have $m + n \in B$ and vice-versa. Also, does vice-versa means that there are ...
1
vote
0answers
31 views

Prove every infinite directed graph has infinite strict linear order or…

I'm trying to prove the following: Every infinite directed graph has an infinite subset of vertices that induces one of the following: a strict linear order a weak linear order an ...
1
vote
0answers
32 views

Monochromatic triangle - graph coloring

I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a ...
1
vote
2answers
65 views

Ramsey number finding constant

Let $K_n$ denote a complete graph with $n$ vertices. Given any positive integers $k$ and $l$, the Ramsey number $R(k, l)$ is defined as the smallest integer $n$ such that in any two-coloring of the ...
2
votes
4answers
134 views

Under what “natural” combinatorial conditions would tetration or higher hyperoperations appear?

This is quite a soft question and is not the same as this question. I want to know what sort of "natural" problems one might examine in combinatorics whose solutions naturally require higher order ...
2
votes
2answers
56 views

“Weak” Ramsey conditions for cardinals

Ok, so these questions just popped into my head and I can't seem to figure it out: Ramsey's theorem tells us that for any $n,r\in\omega$ and any $f:[\omega]^{n}\rightarrow r$, exists an infinite set $...
0
votes
1answer
17 views

$R(x,y)$ is the largest integer such that there is an (x,y)-graph on $R(x,y) $ points

im reading about numbers of Ramsey and I came across a definition that I can not understand.. ...
0
votes
3answers
32 views

Lower bound bound for the Ramsey number $R_k(3,3,…,3)$

The question is: Show that $R_k(3,3,...,3)\geq 2^k+1$. The upper bound part of this problem has been proved in the link How to obtain lower and upper bounds for Ramsey number $R_k (3,3,\dots,3)$, ...
2
votes
1answer
20 views

Strong Folner condition(SFC) implies the existence of a left Følner sequence.

I got stuck with this problem while reading Density in Arbitrary Semigroups by Hindman and Strauss. It says: Problem: If $S$ is a countable semigroup. Then SFC on $S$ implies the existence of a left ...
0
votes
1answer
22 views

all 5-cycle it does not contain neither a triangle nor an independet set of three vertices

Im reading about the Ramsey number, trying to understand the demonstrations of the exact values, in this case my question is about proof of $R (3,6)\leq 18$ in this proof afirme that: all 5-cycle it ...
-1
votes
2answers
33 views

How to show that $g:2^M\to 2^\mathbb{N}$ defined by $g(A) = X\cup A$ is continuous?

In Galvin and Prikry's paper, they inroduce completely Ramsey sets. Definition $5$: A set $S\subseteq 2^\mathbb{N}$ is completely Ramsey if $f^{-1}(S)$ is Ramsey for every continuous mapping $f:2^\...
2
votes
1answer
18 views

Example of $\omega(G \times H) \leq \min\{\omega(G), \omega(H)\}$

It's written in this paper by Alon and Lubetzky that $\omega(G \times H) \leq \min\{\omega(G), \omega(H)\}$, where $\omega$ denotes the clique number, and $\times$ denotes the tensor product on a ...
2
votes
1answer
40 views

Bounds on $d$ for tiling $\mathbb{Z}^d$ with subset of $\mathbb{Z}^n$?

According to this remarkable paper by Gruslys, Leader and Tan, given any subset $T$ of $\mathbb{Z}^n$, $\exists d$ s.t. $T$ tiles $\mathbb{Z}^d$. This immediately became one of my favourite ...
0
votes
0answers
22 views

Existence of disjoint subsets of a family of subsets such that each element appears the same number of times in each

Let $A$ be a set with $n$ elements. Consider a family $B$ of subsets of $A$ i.e. $B\subseteq\mathcal{P}(A)$. How large must $B$ be to guarantee the existence of two nonempty disjoint subsets $X,Y\...
0
votes
0answers
25 views

How does proximality relates to p- limit?

Please help me to solve a problem given in the survey Minimal Idempotents and Ergodic Ramsey theory by Vitaly Bergelson(Exercise 15(iii), page 23), which is Problem: Prove that if $x_1,x_2$ are ...
0
votes
0answers
35 views

How to prove Ramsey Numbers: $R(s-1,t)≤R(s,t)-1$ for $s \geq 3$

I'm trying to prove that $ R(s-1,t) \leq R(s,t)-1 $ for $s \geq 3$. It may be the easy question but I can't prove it. Please give me some hints. Thank you in advance.
1
vote
1answer
42 views

Equivalence of the Multidimensional van der Waerden Theorem

In 'Elemental Methods in Ergodic Ramsey Theory', exercise 1.12, it's asked to show that MvdW4 implies MvdW3, those being the assertions: MvdW3: Let $k \in \mathbb{N}$. For any finite partition of $\...
3
votes
1answer
53 views

Does Ramsey theory prove that all sufficiently long random sequences can be slightly compressed?

First, my apologies if this has already been asked and answered. I did search this community for five to ten minutes looking for similar questions and found none. My lay understanding of Ramsey ...
5
votes
1answer
112 views

isosceles right-angled triangles defined on an infinite Go board by same-colored stones

You start with an infinite Go board. On every point of the board you place one colored stone. There are n>1 different colors. Find all natural numbers n that no matter how the stones colored, three ...
1
vote
0answers
35 views

quadratic grid in which orthogonal triangle formed by grid points [duplicate]

Determine all natural numbers $n$ with $n>1$ that applies: If each grid point of a quadratic grid in the plane is colored with one of n given Colors, then there are always three grid points of the ...
18
votes
3answers
1k views

Triangles defined on an infinite Go board by same-colored stones

You start with an infinite Go board. On every point of the board you place one colored stone. There are $n>1$ different colors. Find all natural numbers $n$ that no matter how the stones are ...
7
votes
1answer
117 views

Ramsey property and linear orders on $\kappa$

I have been trying to solve to prove the following statement: Let $\kappa$ be an uncountable cardinal. The following are equivalent: Every linear order of cardinality $\kappa$ has a ...
1
vote
2answers
78 views

Given positive integers $m,n$, does the Ramsey number $R(m,n)$ always exist?

I recently read some articles about Ramsey numbers and I found them very interesting, I would like to know if there is a test and where I can find it about the existence of these numbers, that is to ...
0
votes
1answer
78 views

Maximum $n$ such that ${n \choose k} \,2^{1 - {k \choose 2}} < 1$ (where $k$ is a constant)

Maximum value of $n$ such that the expression given below does not exceed 1. ($k$ is a constant) $${n \choose k} 2^{1 - {k \choose 2}} < 1$$ Any hints on how to approach this problem. Thanks. ...
5
votes
0answers
55 views

How many n-colour points are needed to force a regularly-spaced set of one colour?

As part of a proof in finding the minimum coloured grid that is guaranteed to have some four points that form an aligned square of one colour, I formed a technique that requires finding the smallest ...
0
votes
1answer
51 views

Understanding the proof of the Generalized Ramsey's theorem.

Generalized Ramsey's Theorem $:$ Given positive integers $k,r,l_1,l_2, \cdots, l_r$ $\exists$ a positive integer $n=R_{*}(k,r,l_1,l_2, \cdots, l_r)$ such that for any $r$-coloring of the $k$-...
0
votes
1answer
69 views

What is the actual statement of Ramsey's theorem?

I am a new to graph theory. In the 4-th lecture given by our instructor Ramsey's theorem was introduced to us. Let $[n]=\{1,2, \cdots , n \}$. He has given the statement as follows $:$ Given ...
-1
votes
1answer
130 views

Van der Waerden's theorem in $\mathbb{Z}^2$

Let $\mathbb{Z}$ be the set of whole numbers and $l,m\in N$. Let's color all elements of $\mathbb{Z}\times\mathbb{Z}$ in $k$ different colors. Prove that we can find two aritmetic progressions $A$ and ...
9
votes
3answers
133 views

Euclidian plane $\pi$ with all points either red, green or blue

In the Euclidian plane $\pi$ all points are either red, green or blue. Prove that you can select three points $A$, $B$ and $C$ from plane $\pi$ so that the the triangle $ABC$ satisfies all the ...
0
votes
1answer
54 views

3 triangles with 3 edges of same color

In the plane for $7$ points distinguish no three points in line. The straight segment connecting any two points is colored blue or red. Prove that there are at least $3$ triangles with $3$ edges of ...
2
votes
1answer
166 views

Lower bound for the Ramsey number $R(3,t)$

Define the Ramsey number $R(s,t)$ to be: $\text{min}\{n \in \mathbb N \mid \text{colouring } E(K_n) \text{ blue and yellow yields a blue } K_s \text{ or a yellow } K_t\}$ Then I am asked to find that ...
3
votes
0answers
39 views

Ramsey's theorem exclusion OR?

Consider Ramsey's theorem: For any $s, t \ge 1$, there exist $R(s, t) < \infty$ such that any graph on $R(s, t)$ vertices contains either an independent set of size $s$ or a clique of size $t$. In ...
1
vote
1answer
121 views

Tic-tac-toe game on the cube 3×3×3

Consider the tic-tac-toe game on the $3\times3\times3$ cube. We know that in this case Player I has a winning strategy. But Player I may not play according to his winning strategy and the game ...
0
votes
1answer
52 views

Ramsey's Theorem(Numerical Example)

Can anybody explain me 7x1 case of R(3,4) = 9(K9, complete graph with 9 vertexes) Ramsey Numbers. Look for table. What's 7x1... Suppose the edges of a complete graph on 9 vertices are coloured ...
1
vote
2answers
43 views

2-coloring of R(m,m) with no monochromatic $K_m$

I am working on a pset question on Ramsey numbers and trying to prove the following question: Let $m \ge 3$ be a positive integer. Construct a red/blue coloring of $K_{(m-1)^2}$ which has no ...
2
votes
1answer
60 views

Has this Ramsey-type function been studied?

Definition. Let $f(n)$ be the least number $m$ such that $$\forall S\subseteq\binom{[m]}3\ \exists X\in\binom{[m]}n\ \forall Y\in\binom X4\ \left|S\cap\binom Y3\right|\in\{0,2,4\}.$$ In human ...
0
votes
0answers
75 views

Ultrafilter proof of the full Hindman theorem

Recall the marvelous proof of Hindman's theorem by Glazer (As can be found here: https://www3.nd.edu/~dgalvin1/pdf/ultrafilters.pdf ). It is proved there that if we partion $N$ to finitely many sets, ...
2
votes
1answer
87 views

Colouring of a grid $\mathbb{Z}^2$.

Colour in the grid $\mathbb{Z}\times\mathbb{Z} = \{(i,j): i,j \in\mathbb{Z}\}$ using $R$ colours. Use Ramsey's Theorem to prove the following: For each $K\geq 1$ there is a monochromatic $K\times K$ ...
1
vote
1answer
95 views

Van der Waerden type theorem

I am trying to understand the proof of that theorem. However, I am not able to comprehend how to use the existense of $\hat{w}(k;r-1)$ and part (iv) of Theorem 2.5 in order to complete the proof.
0
votes
0answers
35 views

Ramsey Numbers with 3 Variables [duplicate]

Define $R(m,n,k)$ and show that $R(3; 3; 3) = 17$ How would I solve this? I am slowly starting to wrap my head around 2 variable ramsey numbers but not quite on 3. Here I know that R(m,n,k) are ...
0
votes
1answer
76 views

Ramsey Number Upper Bound

Prove that if A= R(k,m-1) and B=R(k-1,m) are both even then R(k,m) $\le$ A+B-1 Would be great if someone help in solving this one....
0
votes
1answer
53 views

Probability that in fully connected graph there is a clique of different colors

Actually I got this question in job interview and successfully failed it ( it was obvious eliminating question ). I recall the Ramsey theory and cited the famous result on existence of cliques with ...
2
votes
1answer
51 views

Name of Theorem for Coloring of $\{1, \dots, n\}$

I recently remembered a theorem (I hope I state it correctly) saying that you can color a set of numbers $\{1, \dots, n\}$ with $2^{\sqrt{ \log_2 n}}$ different colors so that for any arithmetic ...
2
votes
2answers
51 views

$2$-coloring of $K_{1,2,2,2,2}$ without monochromatic triangles

According to Turan's Theorem, $K_{1,2,2,2,2}$ is the graph of order $9$ with the maximum number of edges ($32$) that is $K_6$-free. Any (simple) graph $G$ of order $9$ with $33$ edges or more will ...
2
votes
0answers
48 views

What is the Ramsey Number $R(H_k)$ for this special graph $H_k$

Define the graph $H_k$ to be a triangle $xyz$, and $k$ edges $xx_1, xx_2, \dots, xx_k$. Define also for a graph $G$, $R(G)$ to be the least integer $n$ such that a 2-colouring of $K_n$ (the complete ...
2
votes
1answer
253 views

Is it true that $\forall s \geq 2, \forall k \geq 2,\; R_k(s) \leq (R_{k-1}(s))^s$?

Here we denote by $R_k(s)$ the least integer $n$ such that $k$-colouring $K_n$ yields a monochromatic $K_s$ In order to prove another result ($R_k(s) \leq 4^{s^{k-1}}$) I would like to prove the ...
0
votes
1answer
45 views

Prove that the diagonal Ramsey Numbers satisfy $R(s) = O(\frac{4^s}{\sqrt{s}})$

I am given the result $R(s,t) \leq {s+t-2 \choose s-1}$ and asked to 'hence deduce' that $R(s) = O(\frac{4^s}{\sqrt{s}})$ My thoughts currently are: $R(s) \leq {2(s-1) \choose s-1} = \frac{(2s-2)(2s-...
0
votes
0answers
27 views

How to prove this relation between Ramsey Numbers: $R(s,t)≤R(s,t−1)+R(s−1,t)-1$ for $s,t>2$ when $R(s,t-1)$ and $R(s-1,t)$ are even. [duplicate]

I am beginner in combinatorics and have been following this book PRINCIPLE AND TECHNIQUES IN COMBINATORICS by CHEN CHUAN-CHONG. In this book the authors improves the relation $R(s,t)≤R(s,t−1)+R(s−1,t)$...
7
votes
3answers
532 views

Prove that the shortest side of one triangle is the longest side of another, given 3 pairs of points.

I have received this question and am having great difficulties. I don't even know how to try to solve it. It goes like this: 6 points are given in a room. These points are pairwise differently ...