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

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? ...
12
votes
1answer
317 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 ...
11
votes
5answers
766 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 ...
10
votes
2answers
280 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 ...
10
votes
1answer
97 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)$.
7
votes
2answers
136 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
499 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
256 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
216 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
0answers
221 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 !
6
votes
3answers
253 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
1answer
290 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
104 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
166 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.
6
votes
2answers
449 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
169 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
2answers
236 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
0answers
163 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: ...
5
votes
2answers
95 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
3answers
613 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 ...
5
votes
1answer
968 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}$ ...
5
votes
1answer
242 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
525 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 ...
5
votes
1answer
278 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
0answers
127 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
4answers
154 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 ...
4
votes
2answers
148 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
1answer
123 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
320 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
2answers
204 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
88 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
1answer
146 views

A problem in prime number theory

I was wondering if anybody here might provide me with a hint for this rather innocuous-looking problem: If $X:= \{pq: p, q \mbox{ are prime numbers and } p\neq q\}.$ In addition, let us suppose that ...
4
votes
2answers
439 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
3answers
175 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 ...
4
votes
1answer
354 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
127 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 ...
4
votes
1answer
112 views

Arithmetic progression in a subset of $\mathbb N$

What non-trivial sufficient and/or necessary conditions are there for existence an arithmetic progression (finite or infinite length) in an infinite subset of $\mathbb N$.
4
votes
1answer
118 views

Optimal sets for plane coloring problem

There is a reasonably well-known problem: Given a plane with each point colored one of k colors, show there is a rectangle whose vertices are all of the same color, whose axes are parallel to the ...
4
votes
1answer
80 views

Euclidean Ramsey theory problem

Let $k\geq 1$ be given. Consider the following statement: For all (non equilateral) triangles (represented by 3 points in $\mathbb R^2$) and for all $k$-colorings of $\mathbb R^2$ there exists a ...
4
votes
1answer
105 views

Do Ramsey idempotent ultrafilters exist?

I was studying idempotent ultrafilters when I saw that no principal ultrafilter could ever be idempotent, because $\left\langle n \right\rangle \oplus \left\langle n \right\rangle = \left\langle 2n ...
4
votes
0answers
71 views

Arbitrary ratio sequences on a partition of $\mathbb{R}$ (Partition regularity of fixed ratio sequences)

Background: This question arose purely recreationally and doesn't really fit into any context that I know of. Let $A \sqcup B = \mathbb{R}$ be a partition of the ...
4
votes
1answer
125 views

Ramsey number for paths

Let $n = R(P_{r+1}, c)$ be the smallest integer such that if $K_n$ is $c$-edge-coloured, then it contains a monochromatic subgraph isomorphic to $P_{r+1}$, the path of length $r$. I need to show that ...
3
votes
4answers
214 views

Proof of Ramsey Theorem with explicit use of AC

What are minimal axiomatic requirements to prove Ramsey Theorem? This one: Let $X$ be some countably infinite set and colour the elements of $X^{(n)}$ (the subsets of $X$ of size $n$) in $c$ ...
3
votes
1answer
2k views

Show that among 20 people there are either four mutual friends or four mutual enemies

Use the fact that among a group of 10 people, where any two people are either friends or enemies, there are either three mutual friends or four mutual enemies, and there are either three mutual ...
3
votes
2answers
324 views

Permutation of 1…9 with no ascending or descending subsequence of length 4

Arrange the numbers $1,2,...,9$ in such an order that no four of them appear (adjacently or otherwise) in ascending or descending order. Show that there is no arrangement of the numbers $1,2,...,10$ ...
3
votes
1answer
136 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 ...
3
votes
1answer
94 views

Any forest on 5 or more vertices contains an independent set of size 3.

I am looking for a short proof of this fact. This is clearly true by drawing these trees, but I am having trouble putting it into writing. Somehow I need to select 3 of the 5 vertices and show that ...
3
votes
3answers
235 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 ...
3
votes
1answer
214 views

Amalgamation of graphs

I am trying to understand the definition of amalgamation of a $n+1$-partite graph as explained here(first few lines of page 4). We have a $n+1$-partite graph $G$ with partite sets $V_0,V_1,\cdots,V_n$ ...
3
votes
2answers
143 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 ...