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
91 views

What does Ramsey theory tell us?

I have recently started reading about Ramsey theory, though I'm a bit confused about what does it actually tell us. As long as I understood, it says that in a big enough complete graph one can find a ...
0
votes
1answer
95 views

Erdős-Szekeres theorem generalized example showing exactness

I am struggling to understand the following example taken from Seidenberg's paper (1959). "A well-known example of a sequence of $mn$ terms like the following: ...
0
votes
1answer
96 views

Ramsey coloring of $K_{13}$

Arrange the vertices of $K_{13}$ in such a way that they form a regular $13$-gon. Color the edges (which are now either edges or diagonals of the 13-gon) in read and blue, where an edge is colored ...
0
votes
1answer
130 views

Ramsey number inequality proof [duplicate]

Let $2 \leq p \leq q$ and $2 \leq r \leq s$. Prove that $R(p,r) \leq R(q,s)$ and that equality holds if and only if $p=q$ and $r=s$. The equality part is clear, cause we will have $R(p,r) = ...
2
votes
1answer
64 views

Use of pigeonhole principle in ramsey-theorem about monochromatic triangles.

Im trying to prove that for any number n the complete graph with $p(n)$ vertices whose edges have been colored with n colors in some way has a monochromatic triangle (a triplet of nodes that are ...
9
votes
7answers
1k views

An example showing that van der Waerden's theorem is not true for infinite arithmetic progressions

One of the possible formulations of Van der Waerden's theorem is the following: If $\mathbb N=A_1\cup \dots\cup A_k$ is a partition of the set $\mathbb N$, then one of the sets $A_1,\dots,A_k$ ...
1
vote
1answer
71 views

Are some results about coloring positive integers valid for other semigroups?

There are some results in Ramsey theory, which involve additive structure of $(\mathbb N,+)$. For example, if we color the set $\mathbb N$ by finitely many colors, then: There are three numbers ...
0
votes
1answer
92 views

Lower bound for $R(3, 3,\ldots, 3)$

As part of learning Ramsey numbers I am trying to prove that $R(\underbrace{3, 3,\ldots, 3}_{k\text{ times}}) > 2^k$ using the constructive method. In order to do that one needs to colour the edges ...
1
vote
1answer
55 views

Lower bound for the Ramsey number $r(k,k)$

I'm trying to prove the following inequality for every natural $k$: $$r(k,k)>(k-1)^2$$ I was trying to find a blue-red edge coloring of $K_{(k-1)^2}$ without either red or blue $K_k$. Any ...
0
votes
2answers
60 views

The proof of Ramsey's Theorem

I try to understand the proof of Ramsey's Theorem for the two color case. There are still some ambiguities. It says $R(r-1,s)$ and $R(r,s-1)$ exists by the inductive hypothesis. I know the principle ...
1
vote
0answers
29 views

An upper bound on van der Waerden Numbers W(r, k), determined from the Number of Colorings r

Let $W(r, k)$ be a van der Waerden number, such that the interval $[1, W(r, k)]$ contains an arithmetic progression (AP) of $k$ terms, (k > 1), where the integers in the AP all have the same ...
4
votes
0answers
52 views

Find the largest possible value of $n$: color segments connecting any 4 of $n$ points with 4 colors

Let $A_1, A_2, \dots, A_n$ be $n$ points on the plane, no three collinear. Each of the segments connecting two points are colored by one of four given colors. Find the largest natural number $n$ ...
0
votes
0answers
42 views

How injective must these functions be?

Let $S$ be a finite set, and let $b:S\rightarrow\mathbb{N}$ be a function (note, $\mathbb{N}$ includes $0$). For any $K\subset S$ and a function $p:K\rightarrow\mathbb{N}$, let $P_{b,p}$ be the set of ...
1
vote
2answers
52 views

Why the Ramsey number $R(2,4)$ is not equal to $2$?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. Here: I don't understand: For all $2$-colorings, it must have a $K_p$ and $K_q$ or it must have a $K_p$ or a $K_q$? I'm ...
14
votes
1answer
204 views

Congruent quadrilaterals in a tri-colored $72$-gon

I recently watched a movie (A Brilliant Young Mind) in which this problem appeared: Let the vertices of a regular $72$-gon be colored red, blue, and green in equal parts. Show that there are $4$ ...
0
votes
0answers
40 views

Upper limit on Ramsey number $R(a,b)$

How could we prove that if $R(a-1,b)$ and $R(a,b-1)$ are both even then $R(a,b)$ is strictly less than $R(a-1,b)+R(a,b-1)$ or $\begin{equation} R(a,b) < R(a-1,b)+R(a,b-1) \end{equation}$
0
votes
0answers
58 views

Salem Spencer Theorem

The Salem Spencer Theorem seems to be a very interesting combinatorial theorem. This blog motivated me to read more about it. I understand the statement of the theorem, however the proof isn't very ...
0
votes
0answers
29 views

Reference for Ramsey Numbers

Just wondering about diagonal Ramsey numbers $R(n)$. Can anyone provide reference on either of the following? Have there been any notable attempts to make sense of $R(n)$ by using non-combinatorial ...
4
votes
0answers
94 views

Ramsey number $R(K_4,K_4,K_4)$.

I've done a bit of googling, but I can't seem to locate any bounds for $R(4,4,4)$. Here, $R(n_1,n_2,n_3)$ is the generalized Ramsey number where $n_1,n_2,n_3$ are orders of complete graphs. So, in ...
2
votes
1answer
47 views

A question on arithmetic progressions

Is it true that for every $n \in \mathbb N$ , $\exists N \in \mathbb N$ such that for any subset $A \subseteq \{1,2,...,N\}$ , either $A$ or $\{1,2,..,N\} \setminus A$ contains an arithmetic ...
2
votes
2answers
113 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
169 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
83 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. ...
2
votes
1answer
126 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
34 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
49 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
200 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
35 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
37 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
51 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
116 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
119 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
337 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
117 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
75 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
65 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
62 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
32 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
249 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
1answer
43 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
183 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
138 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
84 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
200 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
84 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
90 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
17 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
131 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.