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

1
vote
1answer
83 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
92 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
23 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
40 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
1answer
39 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
42 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
35 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
20 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
38 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
47 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
25 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
133 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
29 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
100 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
60 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
118 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
49 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
66 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
15 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
67 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
43 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
110 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
58 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 ...
0
votes
0answers
73 views

Rado Theorem How do I use it?

Can someone tell me how Rado theorem and/or Ramsey theorem apply to the following problem? Find the smallest positive integer n that satisfies the following: We can color each positive integer with ...
3
votes
1answer
52 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
38 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
138 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
123 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
81 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
17 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
58 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
43 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 ...
2
votes
0answers
26 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
16 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
37 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
59 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
22 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
90 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
110 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?
0
votes
0answers
41 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
72 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 ...
0
votes
0answers
39 views

An easy definition of an $n$-dimensional affine cube

In a few weeks I'm giving a presentation on the History of Ramsey Theory and I want to start off with Hilbert's cube lemma. The only problem is that the pre-requisites for this course is only ...
6
votes
1answer
307 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
37 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 ...
15
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
62 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?
2
votes
2answers
127 views

How can we apply Ramsey's theorem to solve this problem on matrices?

This is from a problem set in a combinatorics course I am taking, and reads as follows: Let $m\geqslant 1$ be an integer. Prove there exists an $n\geqslant 1$ with he following property: every ...
0
votes
1answer
29 views

Upper bound on number of starting positions of a grid coloring game

Let's play a game! The game has the following rules: Let $G$ be a $N\times N$ grid. To each grid square $(x,y)\in G$, assign either $true$ or $false$; call this mapping $C$ (that is, if $(x,y)$ is ...
2
votes
1answer
52 views

Proving an 'obvious' Ramsey upperbound

Here I want to prove the following: $$R(s_{1},s_{2},\ldots ,s_{k}) < R(s_{1}+1,s_{2},\ldots ,s_{k})$$ For $s_{1},\ldots ,s_{k} \in \mathbb{N}$, $s_{i}\geq 2$. (Or can it hold with equality in some ...