Stack Exchange Network

Stack Exchange network consists of 175 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.

5
votes
0answers
46 views

Small & Balanced family of sets

I have the following problem: Let $\epsilon >0$, and $[n] = \{ 1,2,...,n\}$ the set of positive integers up to $n$. There exists a family of subsets $\mathcal{F} \subseteq 2^{[n]}$, such that ...
0
votes
0answers
22 views

Prove that for $m, n \in \mathbf{N}$ with $\ m,n \ge 2 $, we have $\ r(m,n) \le {m+n-2 \choose m-1}$

Prove that for $\ m,n \in \mathbf{N}$ with $\ m,n \ge 2 $, we have $r(m,n) \le \ {m+n-2 \choose m-1}$ Im stuck at this question. I have not understand Ramsey's Theorem fully yet and i cant quite ...
2
votes
1answer
28 views

Particular case of Ramsey's theorem $\mu \rightarrow (\mu)_{\kappa}^{2}$

It's well-know that: If $\kappa$ is a cardinal and $\mu$ is a infinite cardinal, and if we partition $\mu$ into $\kappa$ sets ($\kappa < cof(\mu)$), then one set contains $\mu$ members. In ...
3
votes
1answer
33 views

why $e=e_2+v_i^2+\sum_{j=0}^{\sigma(G)}(i-j)\beta_{ij}(p)$

I need help with this problem: DEF: Let G be a $(3,l)$-graph. We let $v_i=l−1−i$, and we define $s_i$ to be the number of vertices of G of degree $v_i$. Let $G$ be a graph and $p$ a point of $G$. By ...
2
votes
1answer
58 views

Theorem: $e_2\leq (y-1)[\frac{n}{2}-y+1+i]$

Help with this proof: DEF: Let G be a $(3,l)$-graph. We let $v_i=l−1−i$, and we define $s_i$ to be the number of vertices of G of degree $v_i$. Let $G$ be a graph and $p$ a point of $G$. By $H_1$ we ...
1
vote
1answer
25 views

Monochromatic loop in plane

Suppose all the points in the plane are coloured with two colours. Are we guaranteed to find a continuous closed monochromatic path in the plane ? I believe the answer is yes, and then what if ...
1
vote
1answer
29 views

Bounds on Ramsey Numbers

I'm working on a script with a section on Ramsey Theory. I know that $R(s,t) \leq R(s-1,t) + R(s,t-1)$ and that you can add a -1 on the right side if both $R(s-1,t)$ and $R(s,t-1)$ are even. Using ...
3
votes
1answer
77 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
44 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
35 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
46 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
75 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
147 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
60 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
22 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
40 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
22 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
24 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
34 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
28 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
41 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
1answer
33 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
29 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
49 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
56 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
118 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
119 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
97 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
81 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
58 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
77 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
140 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
141 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
61 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
219 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
40 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
161 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
53 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
46 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
64 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
85 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
95 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
99 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
81 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
57 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 ...