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.

0
votes
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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
1answer
100 views

Lower bound for diagonal Ramsey numbers

In the book "The Probabilistic Method" by Alon and Spencer there is a quite clear derivation (provided by Lovasz local lemma) of the fact, that if $ e\binom{k}{2}\binom{n-2}{k-2}\cdot 2^{1-\binom{k}{2}...
0
votes
0answers
12 views

Ramsey Numbers upper and lower bound [duplicate]

Is there an upper and lower bound on R(s,s,s)? In particular, exponential lower bound and upper bound of C^t. I know that R(s,s) has an upper bound of a binomial coefficient (2s-2)C(s-1), and the ...
0
votes
0answers
27 views

Ramsey Number on R3

Let R(s,s,s) be the smallest integer n such that every 3-coloring of the edges of Kn contains a monochromatic Ks. 1) show R(s,s,s) ≤ 27^s 2) calculate an exponential lower bound for R(s,s,s), which ...
2
votes
2answers
50 views

Prove that there are 3 girls and 3 boys such that either they know or they don't know each other

I'm struggling to find a solution to this exercise: Consider a set of 65 girls and a set of 5 boys. Prove that there are 3 girls and 3 boys such that either every girl knows every boy or no ...
1
vote
1answer
47 views

$e(3,6,17)\geq 40$, minimum number of edges possible in an $(3, 6)$-graph on $17$ points

the article is Some Graph Theoretic Results Associated with Ramsey's Theorem for JACK E. GRAVER AND JAMES YACKEL pp: 144-145: https://core.ac.uk/download/pdf/82034211.pdf I'm studying graph theory ...
1
vote
1answer
28 views

Existence of a monochromatic triangle

I have recently learned about Ramsey Theory and I think that sometimes in some olympiads problem it may be a really powerful technique, for example in this problem: A magician has $66$ ...
0
votes
2answers
28 views

Ramsey numbers Special Case

Show that there exists R(s)=N such that all $K_N$ complete graphs (with blue and red two colors) must contain a monochromatic s-vertex star. Find a formula for R(s). I know the formula for cliques on ...
0
votes
0answers
49 views

Suppose that R(s, t − 1) and R(s − 1, t) are both even numbers..

Suppose that R(s, t − 1) and R(s − 1, t) are both even numbers. Prove that R(s, t) ≤ R(s, t − 1) + R(s − 1, t) − 1. I'm trying to learn proofs for graph theory and Ramsey theory but i'm strugging to ...
3
votes
2answers
132 views

Show that, in a group of n people, everyone has the same number of friends if..

Question: Consider a group of n people with the following properties: • no person is friends with everyone, • any pair of strangers share exactly one friend in common, • no three people are ...
0
votes
0answers
40 views

Combinatorics Ramsey Theory Proof

There are 9 passengers on a bus, some know each other. Among every 3 passengers there are two who know each other. Prove that there are at least 5 passengers, each of which knows at least 4 people on ...
1
vote
1answer
29 views

Find the Ramsey number $R(G, P_3)$

Let $G$ be a graph with no isolates and $\lvert V(G)\rvert= m$ such that $\overline{G}$ has a perfect matching. I want to show that $R(G, P_3)=m$ Clearly, $R(G, P_3) \geq \lvert V(G) \rvert = m$, so ...
0
votes
1answer
37 views

In graph 𝐺 with bipartition $A, B$ show the following (see details):

that either (or both) of the following hold when $|A| = |B| > k$: 1) there are adjacent vertices $u \in A, v \in B$ both with degree > k or 2) there are non-adjacent vertices $u \in A, v \in B$ ...
0
votes
1answer
44 views

confused about generalized ramsey numbers

The Ramsey number is stated, where $R(2,3)$ means Ramsey number where there exists a monochromatic clique of size 2 or a monochromatic clique of size 3. I also came to understand that $R(2,3) = N(2,...
6
votes
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 ...
2
votes
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 ...
0
votes
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$?
4
votes
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 ...
0
votes
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 ...
2
votes
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 ...
3
votes
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 ...
2
votes
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 ...
1
vote
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 ...
1
vote
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 ...
3
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
2
votes
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 ...
2
votes
2answers
62 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
68 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
24 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
25 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
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 ...
2
votes
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 ...
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
31 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
55 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
44 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
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 ...
5
votes
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 ...
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
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 ...