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.

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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-...
0
votes
2answers
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 ...
0
votes
1answer
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, ...
1
vote
0answers
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 ...
0
votes
0answers
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.
0
votes
1answer
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?
1
vote
1answer
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?
0
votes
1answer
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 ...
0
votes
0answers
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-...
1
vote
1answer
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}$ ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
25 views

Ramsey Theorem Exercise

Let $r_1<r_2<..<r_s$ and $k$ be positive integers. Prove that there is $n(k; r_1,r_2,...,r_s)$ with the following property. For every colorings of ${[n]}\choose{i}$ with $r_i$ colors, $i=1,......
0
votes
1answer
46 views

Showing a characterization of Ramsey ideals

I'm studying the Filipow and Szuca's article "Ideal version of Ramsey's theorem", and I'm having some problems showing Theorem 3.11. Given a sequence $(x_n)_{n \in \mathbb{N}}$ of on a topological ...
1
vote
1answer
23 views

$S-S$ is syndetic set if $S$ has positive upper density, in the case of group action

Let $G$ be a discrete group. A sequence $\mathcal{F}=\{F_n\}$ is called a $Folner$ sequence if $\frac{|gF_n\Delta F_n|}{|F_n|}\to 0$ as $n\to \infty$ for every $g\in G$. $F_n$ is a finite subset of $...
1
vote
0answers
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:)
0
votes
0answers
17 views

Problem involving recursion of binomial coefficients [duplicate]

Wrt Ramsey numbers I have the following identity given to me: $ R(m, n) \leq R(m-1, n)+R(m, n-1) $ And i have the following bases cases: $R(m,2)=m$ and $R(2,n)=n$. One has to prove that: $R(m, n) \...
0
votes
1answer
34 views

Ramsey theory & Big data problem

How is Ramsey theory used in Big data analysis? Can you suggest me some books or research papers on this subject.
0
votes
1answer
77 views

the k-SRP stationary Ramsey property

I would like to know why here we have $$\kappa<\omega$$ in "where we partition all of $\kappa<\omega$"
1
vote
1answer
108 views

What additional properties does a finite $k$-partite graph have if the endpoints of every edge have a common neighbor in each independent set?

I've been working through a proof for a while now, and I've come across this class of graphs as the output of the algorithm I'm analyzing, however, I've managed to get absolutely nowhere proving any ...
0
votes
0answers
48 views

Upper bound on multicoloured Ramsey number $R^k(n)$ in $k$ colours.

I'm attempting to solve the following exercise, but it's proving quite challenging. I've spent a while on it now and I don't seem to be making any progress. Since it's an exercise at the start of the ...
1
vote
1answer
52 views

For $t \geq 3$, if $n \geq R^{(3)}(t,t)$, then n points in $\mathbb{R}^2$ always contain either t collinear points, or t points in convex position.

Here $R^{(3)}(t,t)$ is the 3-uniform Ramsey number in the two colors red and blue. I'd like to ask for some hints. I've tried giving the 3-sets of $n$ points a meaningful coloring (e.g. red if the 3 ...
1
vote
0answers
49 views

Canonical Ramsey theorem in $m$-uniform setting admits $2^m$ canonical colorings.

This is an exercise I'm doing and I'd like some checking or comments. Given a coloring $c: {\mathbb{N} \choose 3} \to C$, a set $S \subset \mathbb{N}$ is said to be (i) rainbow if no two ...
3
votes
1answer
86 views

Coloring $\mathbb{N}$ with finitely many colors results in monochromatic $x,y,z \in \mathbb{N}$ such that $x+y = z$.

Here are the statements. I have several ideas on how to go about proving them, but I couldn't develop those ideas fully. I'd like to ask for some comments/hints. (i) Show that whenever the natural ...
3
votes
0answers
40 views

van der Waerden with large step size

Suppose we $r$ color $\mathbb{N}$. For what values of $r$ and $k$ are we guaranteed to find a monochromatic $k$ term arithmetic progression $a,a+d,...,a+(k-1)d$ with the additional property that $d&...
5
votes
1answer
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}$...
0
votes
0answers
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$ ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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, ...
0
votes
0answers
16 views

Recurrent relation on Ramsey hypergraph number: for $k \geq 2, s,t \geq k+1, R^{(k)}(s,t) \leq R^{(k-1)}(R^{(k)}(s-1,t),R^{(k)}(s,t-1))+1 $.

I'd like to ask for some checking on my idea of the proof below, in particular the part marked with (*). In our class, we use the following definition of the Ramsey hypergraph number: Given $k \in ...
2
votes
1answer
41 views

When are a set and its complement both syndetic?

Let $G$ be a semigroup. A subset $S\subseteq G$ is syndetic if $G$ is covered by finitely many translates of $S$: i.e. there are elements $g_1,\ldots,g_m\in G$ such that $G=Sg_1\cup \cdots\cup Sg_m$. ...
0
votes
0answers
15 views

What types of graphs have good classical Ramsey properties?

This question is related to the search for classical Ramsey critical graphs. It is well known that circulant graphs have properties which make them good territory for finding these critical graphs. My ...
0
votes
1answer
46 views

Baumgartner's Proof of Hindman's Theorem - Question regarding Lemma 2

I'm trying to work my way through Baumgartner's proof of Hindman's theorem, as published in $\textit{Journal of Combinatorial Theory}$, specifically, a line in the proof of Lemma 2. Definitions $\...
3
votes
0answers
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 ...
1
vote
0answers
86 views

For the multicolour Ramsey numbers, prove that $R_r(t_1,t_2,…,t_r) \leq r^{1 + \sum_{i=1}^r (t_i - 1)}$.

I'm trying to imitate the proof below for the symmetric Ramsey numbers $R(s,s) \leq 4^s$, by looking for an appropriately long right-monochromatic sequence in a $r$-color graph on $r^{1 + \sum_{i=1}^r ...
0
votes
1answer
44 views

Why is total number of cliques and anticliques in a graph correlated with the degree variance?

Given a graph G, a clique is a complete subgraph of G and an "anticlique" is a complete subgraph of the complement of G. When looking for Ramsey critical graphs related to R(k,k) a common objective ...
1
vote
1answer
47 views

Optimal double date groups without seeing anyone twice

Imagine you are hosting a double dating party for straight men and women. There are $2n$ straight men and $2n$ straight women, and you want to pair them into $n$ double dates of 2 men and 2 women each....
1
vote
1answer
29 views

Help Understanding Ramsey's Theorem (Combinatorics)

I've just started studying combinatorics and I'm having a bit of trouble understanding the definition of Ramsey's Theorem that my book gives me. It states, Let $q_1,q_2,...,q_n,t$ be positive ...
0
votes
1answer
65 views

Ramsey Theory - Applying to finite sets

Let $n ≥7$, and let $C$ be a collection of 15 distinct 5-element subsets of [n]. Prove that it is possible to color each element of $[n]$ yellow or orange so that each set belonging to $C$ has ...
7
votes
4answers
526 views

Binomial upper bound for the bi-color Ramsey numbers (Erdős-Szekeres)

The question: How did Erdös - Szekeres came up with a close form with a binomial for the upper bound: Where does the idea behind $R(2,2)=\binom{2+2-2}{2-1}$ - I do see that $R(2,2)=2$ - or $\binom{s+...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
23 views

Counting the number of k-term arithmetic progressions with fixed gap of 2m from [1,n]

Following the proof of finding a lower bound using the probabilistic method for van der Waerden numbers, I'm trying to find the lower bound of a different family. The previously mentioned proof can be ...
2
votes
1answer
122 views

Subsets of $\mathcal{P}_{\infty}\mathbb{N}$ that are open and dense for the Ellentuck topology are completely Ramsey

I am reading Chapter 10 of Albiac and Kalton's book $\textit{Topics in Banach Space Theory}$, and am trying to understand the proof of Theorem 10.1.3, namely that subsets of $\mathcal{P}_{\infty}\...
2
votes
1answer
80 views

Generalisation of infinite Ramsey's theorem to countably infinite or variable edge arities

The usual statement of the infinite Ramsey's Theorem, as appears e.g. in Wikipedia page on Ramsey's Theorem is (paraphrasing slightly): If $X$ is an infinite set, and $C$ is a finite set, and $n$ ...
1
vote
1answer
56 views

$R(p,q)\leq R(R(p − 1, q; r),R(p, q − 1; r); r − 1) + 1.$ it possible to prove? is true?

Has anyone seen this inequality of Ramsey's numbers? where? or is it possible to prove?, I found it in some notes and I don't know if it's true $$R(p,q)\leq R(R(p − 1, q; r),R(p, q − 1; r); r − 1) + ...

1
2 3 4 5
10