Ramsey theory refers to questions of the form "how many objects are needed to guarantee that a given property of the collection holds?"

learn more… | top users | synonyms

2
votes
2answers
69 views

tuple of integers

The integers 1,2,...,30 are invited to a dinner party. They all sit around a round table, in some unknown order. Does there exist an ordering in which there are no three successive (successive means ...
4
votes
1answer
80 views

Brain teaser solution in Graph Theory / Ramsey Theory

I have a solution to the following brainteaser, which I think is the correct answer, but I haven't been able to come up with a way to prove that it's the right answer. I know very little about graph ...
3
votes
1answer
41 views

Calulating the Ramsey number $R(T, K_{1,n})$ of a tree $T$ and bipartite graph $K_{1,n}$

Let $m,n \ge 2$ be such that $m-1$ is a divisor of $n-1$. Let $T$ be a tree with $m$ vertices. Calculate the Ramsey number $R(T,K_{1,n})$. Thoughts: I'm having trouble approaching this question. ...
3
votes
1answer
71 views

Another Evaluation of the Ramsey number $\mathcal{R}(3,3,3)$

The problem Show that $\mathcal{R}(3,3,3)=17$ The story behind the problem and some notation It was first proven by Greenwood and Gleason in 1955 in their paper Combinatorial relations and ...
2
votes
2answers
28 views

Is this equivalent to Szemerédi's theorem?

I know that Szemerédi's theorem states that any set of integers with positive natural density contains arbitrary long arithmetic progressions. However, does this imply that such a set contains an ...
1
vote
1answer
42 views

Graph: What is $R(K_{1,5},K_{1,5})$.

We define $R(H_1,H_2)$ to be the least number such for every graph $G$ with at least $R(H_1,H_2)$ vertices, either $H_1\subset G$, or $H_2\subset G^c$. What is $R(K_{1,5},K_{1,5})$ ? I would say that ...
3
votes
2answers
143 views

Why is the Ramsey`s theorem a generalization of the Pigeonhole principle

German Wikipedia states that the Ramsey`s theorem is a generalization of the Pigeonhole principle source But does not say why this is true. I am doing a presentation about the Ramsey theory and also ...
1
vote
0answers
16 views

Ellis semigroup

I have only seen the construction of the Ellis semigroup applied to a group endowed with the discrete topology. Does the same idea works for any topological group? If not, where does it go wrong? (I ...
0
votes
0answers
14 views

Canonical colorings over $ \omega $

Given a natural number n, let $ c:[X]^n \to \omega $ be a coloring by arbitrary many colors. Then there exists a subset $ H $ of $ X $ for which the restriction of $ c $ to $ [H]^n $ is canonical. ...
4
votes
1answer
33 views

Finding higher Ramsey numbers

How do mathematics go about finding larger Ramsey numbers such as R(5, 5)? How do they find upper bounds on these numbers?
2
votes
1answer
50 views

Proving $R(3,4)\le 9$

I am trying to prove $R(3,4)\le 9$. This is my approach: For any $K_9$ we have (WLOG) at least 4 red edges by the pigeonhole principle. Consider all of the edges between these 4 red edges, if ...
1
vote
1answer
18 views

What is $R(k,l)$?

I'm reading Landman/Robertson's: Ramsey Theory on the Integers. It states the following theorem: Theorem 1.15 (Ramsey's Theorem for Two Colors). Let $k,l \geq 2$. There exists a least positive ...
2
votes
1answer
107 views

A math contest question related to Ramsey numbers

In a group of 17 nations, any two nations are either mutual friends, mutual enemies, or neutral to each other. Show that there is a subgroup of 3 or more nations such that any two nations in the ...
4
votes
2answers
113 views

A Ramsey-type result for families of subsets

Let $S$ be a set of cardinality $\aleph_1$. Consider the directed family $\mathcal{C}$ (here directed means directed with respect to the inclusion) of all countably infinite subsets of $S$. Suppose ...
0
votes
1answer
65 views

Rectangular stained glass window with different colors

Suppose you have six squares of stained glass, all of different colors, and you would like to make a rectangular stained glass window in the shape of a 2 × 3 grid. How many different ways can you do ...
2
votes
1answer
66 views

Prove that any group of 14 people must contain either 5 mutual friends or 3 mutual strangers.

So I think I have the answer to this problem, but there's something about it that's bothering me: Suppose we choose a fixed point with $13$ edges coming out of it. There must be at least $a)$ $9$ ...
3
votes
2answers
60 views

Conjectured diagonal Ramsey numbers

While doing some reading on the Wikipedia page for Ramsey numbers, I stumbled upon OEIS sequence A120414, which lists the allegedly conjectured values of the diagonal Ramsey numbers $R(n,n)$. I ...
2
votes
1answer
51 views

How to computably reduce the number of colors in (infinite) Ramsey's theorem

Suppose we have an "oracle" that gives a homogeneous set for a 2-coloring $\hat c : [\omega]^2 \rightarrow 2$ of pairs of integers. Using this oracle, can we "compute" a homogeneous set for a ...
1
vote
2answers
55 views

Ramsey numbers: if $s_1 \leq s_2$ then $R(s_1,t)\leq R(s_2,t)$

I'm doing this little homework assignment on Ramsey numbers, the question is: Show that $$s_1 \leq s_2 \Rightarrow R(s_1,t)\leq R(s_2,t).$$ I've tried classifying it into these four cases: The ...
0
votes
0answers
25 views

Why is the lower bound 62?

Why is the lower bound of the minimum amount of points needed so that a $4$-coloring leaves at least one monochromatic triangle $62$, and not $66$? A lower bound of $66$ would seem obvious, since it ...
0
votes
1answer
65 views

Ramsey Numbers r(2, n) = n [duplicate]

How do you prove that r(2, n) = n in Ramsey numbers? We have to show that r(2,n)<=n and that r(2,n) >= n.
0
votes
0answers
55 views

Why was the Grahams Number needed?

I did some reasearch about the Grahams number and the proof in which context the number was mentioned as an upper bound. Now I also know that recently this upper bound has been lowered to $2 \uparrow ...
0
votes
1answer
28 views

Combinatorics) Proof concerning Ramsey's Theory

Let $q_1$, $q_2$, ..., $q_k$, t be positive integers, where $q_1$≥t, $q_2$≥t, ..., $q_k$≥t. Let m be the largest of $q_1$, $q_2$, ..., $q_k$. Show that $r_t$(m, m, ..., m) ≥ $r_t$($q_1$, $q_2$, ..., ...
3
votes
3answers
146 views

How would you prove this theory of computation problem?

I have trouble proving the following statement, I'm supposed to do it for our theory of computation course but since I've been trying for days I'm looking for a hint : What is the smallest value ...
0
votes
0answers
37 views

Erdős-Sós conjecture tightest upper bound

The Erdős-Sós conjecture states that any graph of average degree greater than or equal to $k-2$ contains a copy of any tree on $k$ vertices. Does anyone know the current best upper bound on the ...
1
vote
2answers
114 views

For every r exists large enough n such that any graph…

Let $r$ be a natural number. Prove that there exists large enough $n$ , such that every connected graph on at least $n$ vertices contains $K_r$, $K_{1,r}$ or $P_{r}$ as induced subgraphs (first one ...
0
votes
1answer
65 views

Ramsey Numbers and edge coloring

Show that for every $k \in\mathbb{N}$ there exists an $n \in\mathbb{N}$, where $n ≤ 3k!$ such that if $K_n$ is coloured in $k$ colours then we can find in $K_n$ a triangle whose edges are of the same ...
1
vote
1answer
146 views

Girth and monochromatic copy of trees

Question: Prove that for every tree $T$ and every integer $g$ there exists a graph $G$ without cycles of length up to $g$ and such that every two-coloring of the edges of $G$ contains a monochromatic ...
1
vote
0answers
60 views

Principal matrix, Ramsey theorem

Question: Let m be given. Show that if n is large enough, then every n-by-n 0, 1-matrix has a principal submatrix of size m in which all elements above the diagonal are the same, and all elements ...
5
votes
1answer
75 views

Partitioning Integers into Equal Sets to Guarantee Arithmetic Progression

I've run into the following problem which I am sure is true but I cannot prove it: If we color the integers in the set $S = \{1, 2, \ldots, 3n \}$ with $3$ colors such that each color is used $n$ ...
1
vote
0answers
16 views

Equivalence of Theorems; the sphere on $\ell^2$ is finitely oscillation stable.

I just started reading the book Dynamics of Infinite-dimensional Groups, by Pestov, and right in the introduction the following theorem by Milman is cited: Let $\mathbb{S}^\infty$ denote the sphere in ...
3
votes
2answers
87 views

Proving Infinite Ramsey's theorem

I am looking for a proof of the infinite Ramsey theorem which uses the finite Ramsey's theorem. I have been unable to find such a proof. Does there exist such a proof? If so, where can I find it.
1
vote
1answer
45 views

what is the generalization of this problem

$\text{Statement}$: In any partition of $X=(1,2,3,..9)$ into $2$ subsets, at least one of the sets contains an arithmetic progression of length $3$. Can this problem be generalized? In any ...
5
votes
2answers
117 views

A question about infinities and pots of paint

This question is inspired by http://math.stackexchange.com/a/1052384/66307 and quotes from it heavily. Take a countably infinite paint box; this means that it has one color of paint for each positive ...
0
votes
1answer
66 views

Modification of the Ramsey number

Let us denote by $n=r(k_1,k_2,\ldots,k_s)$ the minimal number of vertices such that for every coloring of the edges of the complete graph $K_n$ by $s$ different colors, there is some color $1\le i\le ...
3
votes
1answer
63 views

Verify that R(p,2) = R(2,p) = p, where R is the Ramsey number

Verify that $R(p,2) = R(2,p) = p$, where $R$ is the Ramsey number It just seems obvious that $R(p,2) = R(2,p)$. But why do $R(p,2)$ and $R(2,p)$ both equal p?
3
votes
1answer
39 views

Infinite graphs satisfying a certain Ramsey property

Let $G$ be a countably infinite graph. If $G$ has cliques of arbitrarily large finite size, then $G$ satisfies the following property, which I will call $(*)$: for any $r\in \mathbb{N}$ and any ...
2
votes
1answer
146 views

A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I'm following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an ...
2
votes
2answers
127 views

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and ...
0
votes
1answer
88 views

Monochromatic Solutions

I recently came across this paper: http://borisalexeev.com/pdf/foxgraham.pdf "On Minimal Colorings Without Monochromatic Solutions To a Linear Equation" Can someone explain in clearer terms what ...
0
votes
0answers
27 views

Question about a possible relationship between additive and Bergelson multiplicative upper densities

Let $A \subseteq \mathbb{N}$; let $\mathbb{P} \subset \mathbb{N}$ be the set of all primes. Let $\forall n \in \mathbb{N}, F_n = \{a_n \prod_{i=1}^n (p_i^{r_i}): a_n \in \mathbb{N}, p_i \in ...
1
vote
0answers
60 views

Find n that satisfies the following [duplicate]

Find the smallest positive integer n that satisfies the following: We can color each positive integer with one of n colors such that the equation w + 6x = 2y + 3z has no solutions in positive integers ...
4
votes
1answer
45 views

$4$-cycle of the same color in $K_n$

Let $k$ be a fixed positive integer. All edges of the complete graph $K_n$ are colored in one of $k$ colors. What is the least $n$ such that there always exists a $4$-cycle of the same color? This ...
3
votes
0answers
29 views

Ramsey Upper Bound improvement

I am trying to understand the upper bound that David Conlon produced for the diagonal Ramsey Numbers $$R(n+1,n+1) \leq n^{-c \frac { log n}{log \;{log n}}} \binom {2n}{n}$$ With the binomial theorem ...
1
vote
0answers
17 views

on binary strings without using Ramsey Theorem

Using the Ramsey Theorem Let $X$ be some countably infinite set and colour the elements of $X(n)$ (the subsets of $X$ of size $n$) in $c$ different colours. Then there exists some ...
1
vote
1answer
41 views

Deriving Van der Waerden's theorem from Rado's theorem

In Ramsey Theory Van der Waerden theorem states that, Let $k,r$ be positive integers. Then in every partitioning of the positive integers into $r$ classes there is one class which contains an ...
0
votes
1answer
62 views

combinatorics- persons in group

Let $$ n = \binom {k + b-2}{k-1} \text{ and }k, b\ge 2 $$ Prove that in each group of at least n persons there is k person is familiar with everybody or there are b persons two did not know each ...
1
vote
0answers
22 views

Lower Bound on VDW Numbers

I am trying to find the original proof given by E. Berlekamp that for prime $p$, $$W(p+1) \ge p2^p.$$ All the papers that I have searched only reference this result and give no proof.
1
vote
0answers
23 views

If $m,n$ are integers $\gt 2$ then $R(m,n) \leq R(m-1,n)+R(m,n-1)$ [duplicate]

THIS IS NOT THE DUPLICATE OF ABOVE BECAUSE:I require pigeonhole principle argument to my doubt which is not stated in the answer to above question... I missed my lecture the day the following ...
1
vote
1answer
114 views

Is Graham's number actually valid?

I had a few questions regarding Graham's number and Ramsey theory. I understand what Graham's number is and what it is attempting to solve. My question is, is a hypercube with dimension equal to ...