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

484 questions
Filter by
Sorted by
Tagged with
25 views

### A combinatorial problem in geometry (inequality)

In their 1935 paper, A combinatorial problem in geometry, Erdos and Szekeres prove Ramsey's Theorem. One of the cases is: If $i = 1$, the theorem holds for every $k$ and $l$. For if we select out ...
31 views

### Given $102 \le R(6, 6) \le 165$ is it possible to colour the edges of $K_{200}$ (the compete graph on 200 vertices), using red and blue…

Ramsey number $R(6, 6)$, has been proven to lie between 102 and 165. Given this information, is it possible to colour the edges of $K_{200}$ (the compete graph on 200 vertices), using red and blue, so ...
25 views

### Ramsey numbers proof

Why is it that the inequality: $R(r, b)\leq R(r-1,b)+R(r,b-1)$ holds $\forall r,b \in \mathbb{N}$ Is there some form of conventional proof? Lecturer sent me some notes to have a look at with ...
71 views

### A Graph logical task - Ramsey theory

I have already asked in puzzling.SE this task but from there they pointed to me that it is more a graph question than a puzzle: https://puzzling.stackexchange.com/questions/98396/a-perfect-world-...
36 views

### Prove that there is either a red triangle whose vertices are in S, or a set of 4 points in S such that

Take any set S of 10 points in the plane in which no three are colinear. Color each of the $\binom{10}{2}$ line segments between two of these points with one of red or blue. Prove that there is either ...
35 views

### Explain why there may not be $3$ people with same car.

I don't really understand how to apply Ramsey Theory or the Pigeonhole Principal, so I can't see why this is true: There are $100$ people at a party. Assume each person has an even number of cars, ...
10 views

### Open tools for finding K-cliques in a given graph

I've been trying to calculate some known bounds on Ramsey Numbers through different means, and I kind of fell in love with Kalbfleisch's Construction of Special Edge-Chromatic Graphs (1965). One of ...
28 views

### Proving $R(m + 1, n) \geqslant R(m, n)$ for all $m, n \geqslant 2$

Is the Ramsey number $R(m + 1, n) \geqslant R(m, n)$ for all $m, n \geqslant 2$? Briefly justify your answer. Can anyone help me with this please? Many thanks.
24 views

### Is the Ramsey number $R(m + 1, n) \ge R(m, n)$ for all $m, n \ge 2$

Is the Ramsey number $R(m + 1, n) \ge R(m, n)$ for all $m, n \ge 2$. I'm having trouble proving this inequality. Could anyone offer a hint?
46 views

### It is known that the Ramsey number $R(4, 4)$ equals 18. Show that $R(4,5) \le 33$.

It is known that the Ramsey number $R(4, 4)$ equals 18. Show that $R(4,5) \le 33$. I'm stumped by this question, so could someone please offer a hint?
37 views

### Question on a proof of Ramsey's Theorem

How do some Ramsey's Theorem proofs get to proving the inequality: $R(s, t) \le R(s − 1, t) + R(s, t − 1)$ I get how the result shows, in the end, that there is a finite $R(s,t)$ but what's the ...
26 views

### Prove a strengthening of the existence of Ramsey Graphs

Assumption: For any graph $H$ there is a graph $G$ where any 2-coloring of $G$ either has $H$ colored 1 or $H$ colored 2. Want to show: For any graphs $H_1,H_2$ there is a graph $G$ where any 2-...
98 views

### Ramsey number problem

Let $K_{n}$ is the complete graph on $n$ vertices and $T_{m}$ is a tree on $m$ vertices How do I show that $R(K_{n} , T_{m}) = (n-1)(m-1) + 1$? Here $R(G,H)$ is the minimum $t \in \mathbb{N}$ ...
19 views

### Probability that there are either $k$ mutual friends or $k$ mutual enemies in a group of $n$ people?

I'm trying to wrap my head around a proof presented in Rosen's Discrete Mathematics and its Applications that relates to the lower bound for the Ramsey number $R(k,k)$. I'm comfortable with majority ...
64 views

### What is the minimum number of vertices a graph must have to have two triangles, two 3-independent sets, or one of each?

I am trying to figure out what the minimum number of vertices a graph must have in order guarantee that it has two triangles (3-cliques), two 3-independent sets, or one of each. Two cliques or ...
25 views

27 views

### Schur's theorem and numbers

Can you give a proof for bounds of Schur's numbers? Please suggest me articles to have better idea of Schur's theorem(Ramsey theory). Thanks in advance:)
17 views

190 views

### Upper Bound on Ramsey $R(k)$

If $R(k)$ is the minimum number of vertices that ensures a monochromatic $k$ clique in an arbitrary 2 coloring of $K_{R(k)}$ (Complete Graph), I read a proof that establishes an upper bound of $2^{2k}$...
13 views

### Notation in infinite Ramsey Theory

I am following the notes here and am confused about some notation specifically on page 24. It defines sets: $(A,M)^{(\omega)} = \{ L\in \mathbb{N}^{(\omega)}$ | $A$ is an initial segment of $L$ ...
15 views

### Proof of canonical Ramsey theorem by colour patterns of $4$-sets.

I'm reading this proof (theorem 1.5) of the canonical Ramsey theorem, which analyses the colour patterns of the subsets of $4$ elements of $\mathbb{N}$. I'd like to ask for some clarification. In ...
28 views

### Lower bound of the Ramsey number $R(k,l)$ using probabilistic argument.

I'd like some hints for the following exercise. My guess is that the RHS is the number of vertices of a graph without a red $K_l$ or a blue $K_k$. If we interpret $p$ as the probability that an edge ...
41 views

### Deduce the finite Ramsey theorem from the infinite case.

I'd like to ask for some checking of my proof for the statement below. Using the fact that every $\textbf{red/blue}$ colouring of $\mathbb{N} \choose 2$ contains an infinite monochromatic clique, ...
16 views

76 views

### Oriented graphs with no infinite paths

This question is based on a deleted question by user Ethan. I don't think it's what Ethan originally meant to ask, but I thought it was an interesting question. Let $G = (V,E)$ be an infinite (simple ...
86 views

46 views

### Is this proof valid? Infinite Ramsey theorem from the finite

It has been stated in many places (e.g. here) that the infinite Ramsey theorem cannot be deduced from the finite. I seem to have found a proof of finite -> infinite via a standard compactness argument ...
52 views

### Seating arrangement with no two enemies adjacent

There are 50 people at a party. Each person is (mutually) enemies with exactly 24 people. Show that if they all sit at a circular table, a seating is possible such that no 2 people who are enemies ...