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

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? ...
14
votes
5answers
2k 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 ...
14
votes
1answer
1k views

Graham's Number : Why so big?

Can someone give me an idea of how R.Graham reached Graham's Number as an upper bound on the solution of the related problem ? Thanks !
14
votes
2answers
621 views

How many 2-edge-colourings of $K_n$ are there?

I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
14
votes
1answer
661 views

Monochromatic squares in a colored plane

Color every point in the real plane using the colors blue,yellow only. It can be shown that there exists a rectangle that has all vertices with the same color. Is it possible to show that there exists ...
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$ ...
11
votes
1answer
156 views

Coloring of positive integers

Suppose $f:\mathbb{Z}^+\longrightarrow X$ is a function, with $X$ a finite set. Is it true that there are $a,b\in\mathbb{Z}^+$ such that $f(a)=f(b)=f(a+b)$.
10
votes
1answer
358 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: ...
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$ ...
7
votes
2answers
153 views

Every 33-length subsequence of $1,2,\dotsc,122$ contains a three term arithmetic progression

Is it possible to prove that every 33-length subsequence of the sequence $1,2,3,\dotsc,122$ contains a three term arithmetic progression? Maybe I should post it on mathoverflow
7
votes
1answer
988 views

Showing that $K_7$ contains at least 4 monochromatic triangles

A problem in my book is: Let the edges of $K_7$ be colored with the colors red and blue. Show that there are at least four subgraphs $K_3$ with all three edges the same color (monochromatic ...
7
votes
1answer
2k views

Prove Ramsey Number R(3,5)=14

I'm having problem proving the ramsey number of R(3,5) = 14. Below is my proof. Proof. Let $v_0$ be a vertex from a $k_{14}$ vertices. The vertices incident to $v_0$ are $v_1, v_2, \cdots , v_{13}$ ...
7
votes
1answer
162 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 ...
7
votes
1answer
333 views

What is the proof of the “thin set theorem”? A result in infinite Ramsey theory.

OK so here's a precise question: Is it true that for every integer $k\geq1$ and every $f:\mathbb{Z}^k\to\mathbb{Z}$, there is some infinite subset $A\subseteq\mathbb{Z}$ such that $f(A^k)$ is not all ...
7
votes
1answer
240 views

Closest pair of vectors in $\{0,1\}^n$

Suppose we are given $k$ points in $\{0,1\}^n$ (using Hamming distance as metric). Consider the two points that have the smallest distance between them. Does there exist any results bounding this ...
7
votes
2answers
253 views

Prove that $r(k,k) + k \leq r(k + 1, k + 1) $

Prove that $r(k,k) + k \leq r(k + 1, k + 1)$, where $r(k,l)$ is the minimum number of vertexes in a Graph, where we have a clique with $k$ vertexes or a stable set with $l$ vertexes. There are ...
6
votes
3answers
429 views

Does a red/blue coloring of the infinite subsets of $\mathbb{N}$ necessarily give an infinite monochromatic $M\subset \mathbb{N}$?

The infinite Ramsey theorem states that for any $n$, if all the subsets of $\mathbb{N}$ of size $n$ are colored red/blue, then there is an infinite $M$ all of whose subsets of size $n$ are ...
6
votes
3answers
1k views

Good way to learn Ramsey Theory

What are some good books on Ramsey theory? I have Van Lints book on Combinatorics: is this enough preparation to start reading about Ramsey theory? I want a book that includes important results and ...
6
votes
1answer
358 views

Known bounds and values for Ramsey Numbers

Is there a good online reference that lists known bounds on Ramsey numbers (and is relatively up to date)? The wikipedia page only has numbers for $R_2(n,m)$. I am specifically interested in known ...
6
votes
2answers
167 views

Two subsets and their union have same color

Color all nonempty subsets of $[n] = \{1,2,\ldots,n\}$ with colors $1,2,\ldots,r$. Show that, for all large enough $n$, there exist two disjoint nonempty subsets $A,B \subseteq [n]$ such that ...
6
votes
1answer
411 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 ...
6
votes
2answers
721 views

Proof of the van der Waerden theorem

The van der Waerden theorem states that given any natural numbers $k$ and $r$, there exists a natural number $W=W(k,r)$ such that if the set $\{1,2\cdots W\}$ is divided into $r$ classes (also called ...
6
votes
1answer
215 views

Ramsey theory, finite colourings of $\mathbb{N}$ and infinite monochromatic sets

I am trying to show that the following statement is false: whenever $\mathbb{N}$ is finitely coloured by $c: \mathbb{N} \to \{1,\ldots,k\}$ (in the sense of Ramsey theory), there exists an infinite ...
6
votes
1answer
742 views

Understanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.

I was reading the Wikipedia article on Friedman's finite form of Kruskal's tree theorem, and am interested in the large numbers TREE(n). I would like to verify TREE(2)=3 myself, but find conflicting ...
6
votes
2answers
265 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 ...
6
votes
0answers
216 views

Ramsey (graph) theory question with tree and girth

Sorry for the abundance of questions I'm asking. Test is soon... Prove that for every tree $T$ and every $g \in \mathbb{N}$, exist $G$ with girth $g$, so that in any 2-edge-coloring of $G$ there is a ...
5
votes
4answers
935 views

How long does a sequence need to be to be guaranteed to have a monotonic subsequence length k?

The sequence 7, 2, 4, 1, 4, 8 has an increasing subsequence length four (2, 4, 4, 8) and a decreasing subsequence length three (7, 4, 1). It has other monotonic (increasing or decreasing) subsequences ...
5
votes
2answers
126 views

Old exam question about well ordering on $\mathbb{R}$

I am not sure how to start tackling this question and would love a hint: Let $<$ the regular order relation on $\mathbb{R}$, and $<_w$ well ordering on $\mathbb{R}$. We define a coloring ...
5
votes
1answer
244 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 ...
5
votes
2answers
215 views

Any partition of $\{1,2,\ldots,9\}$ must contain a $3$-Term Arithmetic Progression

Prove that for any way of dividing the set $X=\{1,2,3,\dots,9\}$ into $2$ sets, there always exist at least one arithmetic progression of length $3$ in one of the two sets.
5
votes
2answers
124 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 ...
5
votes
3answers
223 views

Erdős Probabilistic method

My question is based on the Erdos probabilistic method. I am trying to read from the paper here. The proof of Theorem 1 contains the statement Since a block sequence is monochromatic with ...
5
votes
1answer
302 views

What's the difference between Ramsey theory and Extremal graph theory?

Wikipedia teaches us that problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?" It ...
5
votes
1answer
358 views

An upper bound for a graph Ramsey number

I am trying to prove the following result, given as an exercise in my book: $r(K_m+\bar{K_n},K_p+\bar{K_q})\le\binom{m+p-1}{m}n+\binom{m+p-1}{p}q$. Here $r(G,H)$ denotes the Ramsey number for the ...
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$ ...
5
votes
0answers
218 views

number of potential couples

A potential couple is a pair of a man and a woman that like each other (assume that 'like' is a symmetric relation). Given a group of $M$ men and $W$ women, I want to know how many different ...
4
votes
3answers
479 views

Does “Big Data” Have a Ramsey Theory Problem?

I'm erring on the side of conservatism asking here rather than MO, as it is possible this is a complex question. "Big Data" is the Silicon Valley term for the issues surrounding the huge amounts of ...
4
votes
2answers
264 views

Counterexample for $R(4,4) \neq 8$

I try to find a counterexample for $R(4,4)\neq 8$. (R is the Ramsey-number). I drew a graph with 8 vedges and I coloured all edges $(v_i,v_j)$ with $i-j =\pm 2,4,6$ in the same colour (for example ...
4
votes
2answers
592 views

What is Ramsey Theory ? what is its own importance in maths?

3 days ago , i had a discussion with a close friend who studies physics - still a student - . and i was telling her about the biggest known numbers in maths , so i told her about numbers such googol ...
4
votes
1answer
129 views

There exist $\{a_{n}\},\{b_{n}\}$ such $\lim_{n\to\infty}\frac{a_{n}}{b_{n}}=c?$

Let $ A$ and $ B$ are two infinite subsets of the natural numbers $\mathbb{N}$, such that $$A\cap B=\emptyset \qquad A\cup B=\mathbb N$$ Question: is it true that for every natural $c>0$, ...
4
votes
2answers
328 views

Guaranteeing an integer lattice point centroid

My question is this: Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$. I ...
4
votes
2answers
99 views

Crowding the boundary of non-constructivity without crossing it?

Can any sense be made out of my vague feeling that some proofs in Ramsey theory are as close as you can get to non-constructive proofs without crossing the line? Is there any way to make this ...
4
votes
2answers
380 views

Given an infinite poset, show that it contains either a infinite chain or an infinite totally unordered set. [duplicate]

Been thinking about this one for awhile and I'm still stuck... Thought about proving it by arriving at a contradiction but I haven't reached anything noteworthy. If you do a proof by contradiction, ...
4
votes
1answer
175 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 ...
4
votes
2answers
616 views

how to construct 17-vertexed graph for Ramsey number R(3,6)=18

Ramsey number $R(3,6)=18$. How to construct a graph of $17$ nodes which does not contain neither a clique of order $3$ or an independent set of order $6$. could you show me the tactics or 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 ...
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 ...
4
votes
2answers
162 views

Affine Van der Waerden's theorem

I have the following statement which is claimed to be a version of Van der Waerden's theorem: For any finite partition of $\mathbb{N}$, one of the cells contains affine images of every finite ...
4
votes
1answer
381 views

Ramsey number for books

Given a triangular book $B_n$ I am trying to prove that $r(B_n,B_n)\le 4n+2$ where $r(B_n,B_n)$ is defined as the least positive number such that any graph $G$ on $r(B_n,B_n)$ vertices either has a ...
4
votes
1answer
150 views

Edge coloring a graph to find a monochromatic $K_{2,n}$

I am trying to prove or disprove the following statement: Let $n>1$ be a positive integer. Then there exists a graph $G$ of size 4n-1 such that if the edges of $G$ are colored red or blue, no ...