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

0
votes
0answers
26 views

Is there an arbitrarily large set of naturals so that the sum of each two has exactly $n$ prime divisors? What about an infinite set? [on hold]

Is there an arbitrarily large set of naturals so that the sum of each $2$ has exactly $n$ prime divisors where $n$ is fixed? What about an infinite set? For $n=1$ this is clearly false, what ...
-1
votes
1answer
36 views

an edge coloring of $k_{16}$ with no monochromatic triangle [on hold]

My plan is to show that $R(3,3,3)$ is more than 16. So, i want to prove it with graph-theory. i know i should find an edge coloring of $k_{16}$ which contains no monochromatic triangles. Can anyone ...
0
votes
1answer
20 views

can we find a $k_4$ colored with 1 color in a $k_8$ which is colored with just 2 colors?

Assume that we define edge coloring in this way : An edge coloring of a graph is an assignment of "colors" to the edges of the graph. So, now imagine we have a $K_8$ which has edges colored with just ...
1
vote
1answer
58 views

Uses of Ramsey Theory in Astronomy?

In the last paragraph of a Scientific American article of July 1990 that can be found here http://www.math.ucsd.edu/~ronspubs/90_06_ramsey_theory.pdf Graham and Spencer write "Today we can easily ...
2
votes
1answer
58 views

Ramsey counter examples

I do not know of any solution or if it's an open problem: Let $R(i,i)=k$, therefore there exists a counter examples with blue and red edges for a clique of size $k-1$. Does there exist a ...
3
votes
1answer
57 views

Infinitely many points in plane s.t. no point is a convex combination of other points

Let $A$ be an infinite set of points in the plane, with no three points of $A$ collinear. I want to prove that $A$ contains an infinite set $B$ such that no point of $B$ is a convex combination of ...
0
votes
0answers
25 views

Monochromatic triangle in two closed set which cover the plane

I am reading Section on Euclidean Ramsey Theory in Ronald Graham's Rudiments of Ramsey Theory. Exercise 7.3 states that Show that if $E^2$ is covered by two closed sets of colors then every ...
5
votes
1answer
63 views

in every coloring $1,…,n$ there are distinct integers $a,b,c,d$ such that $a+b+c=d$

Prove that for every $k$ there is a finite integer $n = n(k)$ so that for any coloring of the integers $1, 2, . . . , n$ by $k$ colors there are distinct integers $a, b, c$ and $d$ of the same color ...
0
votes
1answer
34 views

Show that in any group of 9 people there is always a subgroup of 3 mutual strangers or a subgroup of 4 mutual acquaintances.

Show that in any group of 9 people there is always a subgroup of 3 mutual strangers or a subgroup of 4 mutual acquaintances. I know that this is an application of Ramsey's Theorem, but I'm not sure ...
3
votes
2answers
78 views

What are some important applications of the Erdős-Szekeres Theorem?

Erdős-Szekeres Theorem: Any finite sequence of $n^2+1$ real numbers contains a monotonic subsequence of length at least $n+1$. I was wondering what are the most important applications of the ...
0
votes
1answer
67 views

Lower bound for Ramsey numbers: $R( n + 2 , 3 )>3n$

I need to prove the following inequality: $$R( n + 2 , 3 )>3n$$ where $n>1$ and $R(s,t)$ is a Ramsey number. The most general way to prove such inequalities is to paint a graph with $3n$ ...
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 ...
2
votes
1answer
87 views

Proof involving Ramsey numbers

$S$ is a set of R(m,m;3) points in the plane in which no 3 points are collinear. I am trying to prove that $S$ contains $m$ points that form a convex $m$-gon. I have tried using similar logic to the ...
0
votes
0answers
21 views

Ramsey number for tree and complete graph [duplicate]

I am having a lot of trouble understanding Ramsey theory. I am working on an exercise that asks for the Ramsey number $R(T,K_{1,n+1})$ where $T$ is a tree with $m$ edges and $n$ is a multiple of $m$. ...
0
votes
1answer
12 views

Independent Set of Product Graph and Ramsey Number

For two graphs $G,H$, define $G\otimes H$: it has vertex $V(G)\times V(H)$, $(v_1,v_2)(v_1',v_2')\in E(G\otimes H)$ if it satisfies all the following three requirments (i) $(v_1,v_2)\neq (v_1',v_2')$ ...
4
votes
0answers
38 views

Maximum $K_6$-free graph on $15$ vertices?

My question is, suppose we have $15$ vertices. What is the maximum number of edges we can add between these vertices, each with a fixed colored red or blue, so that there is no monochromatic triangle? ...
1
vote
0answers
104 views

Finding the exact value for $H(7)$

The graphs that I work with are all complete, each edge is colored red or blue, and each vertex is colored red or blue. $\textbf{Definition:}$ A graph is $\textit{Happy}$ if there exists a vertex ...
1
vote
1answer
67 views

Finite coloring of $[\omega]^{<\omega}$.

It is known that Ramsey theorem does not hold for finite colorings of $[\omega]^{<\omega}$. So I am interested in this "partial" result: First let $S_n = ]n, +\infty[$ be the set of natural ...
2
votes
1answer
45 views

Find maximal clique in an multigraph with $n$ vertices, where each vertex is colored with $k$ colors.

You are given a multigraph with $n$ vertices. Every vertex is colored with maximum of $k$ colors. If two vertices share a color, there is an edge between them which is colored with that color. (A pair ...
1
vote
0answers
97 views

Number of edges needed for bad colouring in graph Ramsey theory

Given $n$, consider the complete graph $K_{R(n)-1}$, where $R(n)$ is the diagonal Ramsey number. So there exist $2$-colourings of the edges of $K_{R(n)-1}$ without a monochromatic copy of $K_n$. ...
1
vote
1answer
33 views

A Ramsey not Completely Ramsey Set of $[\omega]^\omega$.

Let $a \in [\omega]^{<\omega}$ (a finite subset), $A \in [\omega]^{\omega}$ (an infinite subset). Let us define $$[a, A] = \{a \cup B: B \in [A]^{\omega} \wedge max(a) < min(B) \}.$$ These ...
1
vote
0answers
36 views

Aplication of Ramsey theory in group theory

Let $G$ be a infinite group. How to show that there is a $A\subseteq G$ infite such that $$\forall x,y,z\in A\;\; \big(xy=z\Leftrightarrow (x=y=z=x^2)\big)$$ I've tried to define the coloring ...
1
vote
1answer
70 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 ...
1
vote
1answer
12 views

Asymptotic lower bound for R(k,k)

I'm reading Spencer's lectures on the probabilistic method. Using the Lovasz local lemma, we've shown that $R(k,k)>n$ if $$ 4{k \choose 2} {n \choose k-2} 2^{1-{k \choose 2}} < 1. $$ Now I'm ...
2
votes
1answer
79 views

Pigeon-Hole Principle Common Sum

Each of 15 red balls and 15 green balls is marked with an integer between 1 and 100 inclusive; no integer appears on more than one ball. The value of a pair of balls is the sum of the numbers on the ...
0
votes
0answers
20 views

Problem on Ramsey Numbers

I want to prove that $R(3,5) = 14$. I think the easiest first step is proving $R(3,5) \leq 14$ since I think developing a counterexample on 13 vertices would be cumbersome. Let's say the two edge ...
0
votes
1answer
36 views

$n$ distinct real numbers has a monotone subsequence of length $k$ if $n \ge (k-1)^2 + 1$

I'm working through some problems and I just completed the proof that if $n\ge R(k)$ for a sequence of distinct real numbers $a_1, a_2, a_3, ..., a_n$ has a monotone subsequence of length $k$, that is ...
1
vote
1answer
26 views

Prove that there is a red triangle or a blue triangle that is is a sub-graph

If the edges of $K_6$ are coloured blue or red, prove that there is a red triangle or a blue triangle that is a sub-graph. Well I am having a hard time proving this, I try to prove it by ...
10
votes
1answer
334 views

van der Waerden's original proof

I am looking for a book/site which has the English translation of the proof of van der Waerden's theorem as presented by van der Waerden himself. In other words is the translation of the paper: ...
0
votes
1answer
39 views

How to create a matrix in Hammersley's proof for Erdős-Szekeres Theorem?

Hammersley gave the following algorithm that proves the theorem. Let a sequence $a_1,a_2,...,a_{n^2+1}$. (a) let $a_1$ start the first column and for $i\ge 1$ (b) if $a_i$ is greater than or equal ...
0
votes
1answer
73 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: ...
1
vote
1answer
81 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
87 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
118 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
59 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 ...
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? ...
6
votes
2answers
254 views

Is there a simpler proof of Van der Waerden's Theorem when there are only two colors?

http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem The usual approach is to induct on the length of the arithmetic progression, which is difficult to simplify directly to the case of two ...
4
votes
1answer
172 views

Van der Waerden without topological dynamics?

Applying topological dynamics to prove Van der Waerden's theorem on the existence of monochromatic arithmetic progression has now become a somewhat classical example of the power of topological ...
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$ ...
5
votes
1answer
239 views

example of a finite coloring without infinite monochromatic set closed under addition

I am studying some theorems on combinatorial set theory, especially Ramsey theorem and Hindman's theorem. I think I am going to ask a silly question, but I am too much involved in the subject to think ...
0
votes
1answer
84 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
45 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 ...
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 ...
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$ ...
4
votes
1answer
137 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
0
votes
2answers
57 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
20 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
51 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 ...
14
votes
5answers
1k views

Why König's lemma isn't “obvious”?

I keep facing König's lemma "Every finitely branching infinite tree over $\mathbb{N}$ has infinite branch". Why it is not taken "obvious" but needs a careful proof? It seems somewhat obvious, but I ...