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

414 questions
1answer
41 views

### Prove $R(t,t) \ge 2^{t/2}$ for all $t\ge 3$

Prove $R(t,t) \ge 2^{t/2}$ for all $t\ge 3$. I'm thinking about using induction. Base case: R(3,3)=6, which works. Inductive Step: I claim $\frac{R(t+1,t+1)}{R(t,t)} \ge \sqrt{2}$, which is true ...
0answers
49 views

### Proof of familiarity between 9 people

How can we try to prove that among any 9 people thare are 3 people who are familiar with each other or 4 who are not familiar with each other? My approach: I try to convert this to graph theory. So ...
3answers
51 views

### If $K_{14}$ is colored with two colors, there will be a monochromatic quadrangle.

This question is from Problem Solving Strategies by Engel, Chapter 4 question 50. If $K_{14}$ is colored with two colors, there will be a monochromatic quadrangle. Here, $K_{14}$ is the complete ...
1answer
100 views

1answer
198 views

### Prove: $[k+y-1-v]{v \choose k}\geq \sum_{j=0}^a(-1)^j \left( \sum_{i=0}^k{v-i \choose k-i}r_i(j)\right)+\epsilon(a,k,p)$

I'm studying the ramsey numbers, especially $R(3,6)=18$ for Graver and Jackel, and i have tried to understand the theorem $2$ for quite some time but I have not succeeded. Theorem 1: Let $G$ be a ...
1answer
32 views

### If a set has infinitely many multiples of each integers, then it intersects (S-S) for any set S with positive upper density

I wanted to know whether above statement is true. If it is, how can one go about proving it? Say A $\subset\mathbb{N}$ is a set such that $\forall$ k $\in\mathbb{N}$ , A contains infinitely many ...
1answer
57 views

### Ramsey Number $R(4,4) = 18$

I wanted to know how to prove that $R(4,4)= 18$ without having to draw the graph. I assume that I will have to start by proving that $R(4,4) \geq 17$. Can I also prove it by using $R(3,4) = 9$?
0answers
64 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 ...
0answers
28 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 ...
1answer
33 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 ...
1answer
47 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 ...
1answer
68 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 ...
1answer
30 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 ...
1answer
39 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 ...
1answer
85 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 ...
2answers
46 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 ...
0answers
43 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 ...
0answers
71 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 ...
2answers
85 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 ...
4answers
155 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 ...
2answers
62 views

1answer
37 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 ...
1answer
42 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 ...
1answer
33 views

1answer
62 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 ...
1answer
119 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 ...
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 ...
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 ...
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 ...
2answers
119 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 ...