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
32 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 ...
0
votes
0answers
46 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
182 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
32 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 ...
2
votes
0answers
35 views

Canonical colorings over $ \omega $

Given a natural number n, let $ c:[X]^n \to \omega $ be a coloring by arbitrary many colors, where $X$ is an infinite countable set. Then there exists an infinite subset $ H $ of $ X $ for which the ...
4
votes
1answer
45 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
99 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
24 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
127 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
117 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
235 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
92 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
71 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
62 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 ...
0
votes
1answer
59 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
30 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
169 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
72 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
37 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
170 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 ...
1
vote
2answers
120 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
81 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
178 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
81 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
88 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
115 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
51 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
122 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
86 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
98 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
42 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
206 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
146 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
133 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 ...
4
votes
1answer
50 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
33 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
20 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 ...
2
votes
1answer
58 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
63 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
23 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
168 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 ...
1
vote
1answer
227 views

Chromatic Triangles on a k17 graph

If the edges of the complete graph K17 (on 17 vertices with no three collinear) are each colored one of three colours can it be proven to have two or more monochromatic triangles?
1
vote
0answers
105 views

Algebra in Erdős's proof of lower bound for Ramsey number

A well known proof by Erdős shows a lower bound on the Ramsey number $r(k,k)$ using the probabilistic method. The theorem goes thusly: Let $n,\, k\in\mathbb{N}$ such that ${n \choose k}2^{1-{k ...
3
votes
2answers
84 views

Ramsey Numbers involving Cycles, $R(K_3, C_5)$

I've been asked to determine the value of $R(K_3, C_5)$, but I'm having a lot of difficulty putting all the pieces together. We were given the hint of using $R(3,4) = 9$, and I've tried to apply ...
6
votes
1answer
389 views

What is the explanation for the $64$ in Graham's number $g_{64}$?

As in, why does the iteration of the function until $g_{64}$ guarantee this property that defines Graham's number? Why was this number chosen? If I had to guess (emphasis on guess), I'd say that the ...
1
vote
0answers
40 views

Probability that a subset of a degree-regular graph shares at least a certain number of mutual connections

Consider a set of $n$ vertices of common degree $p$. What is the probability that some subset of $x$ vertices from $n$ share $q$ mutual connections within that group of size $x$? i.e. If we have ...
17
votes
1answer
2k views

Why are there only a few known Ramsey numbers?

Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test? ...
3
votes
0answers
69 views

Conjectured Value of Ramsey Number $R(3,10)$

It is known that the value of the Ramsey number $R(3,10)$ is either 40, 41, or 42. Have any experts in the field offered a conjecture as to which it might be?