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

6
votes
2answers
507 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 ...
1
vote
2answers
181 views

Ramsey theory - colouring of edges

I'm trying to understand a proof: $R(3,3) = 6$ proof: Take a red/blue colouring of $K_6$. Take a vertex $v$ (is an element of) $V(K_6)$, either $v$ is incident to $\geq 3$ red edges or, $v$ is ...
1
vote
1answer
100 views

Prove the following inequality: $N(P,P,2)\leq 4^{P-1}$

I've made very little headway on this problem, so any help is appreciated. Edit: Sorry, I should have explained that. In general, $N(p,q,2)$ is the smallest value of $n$ such that a red-blue ...
1
vote
1answer
89 views

Hales Jewett regularity theorem

I am trying to read the Hales-Jewett regularity theorem given as Theorem 1 here. I have a doubt in the proof which I am hoping someone here can clarify. Here are some background definitions and a ...
0
votes
3answers
642 views

Party problem / Ramsey's theorem R(3,3)

I'm looking for an algorithm that solve Party problem. The party problem asks to find the minimum number of guests that must be invited so that at least 3 will know each other or at least 3 will not ...
3
votes
1answer
134 views

Van Der Waerden without topological dynamics?

Applying topological dynamics to prove Van Der Waerden's theorem on the existence of monochromatic arithematic progression has now become a somewhat classical example of the power of topological ...
1
vote
1answer
231 views

Combinatorial Set Theory - Ramsey's Theorem Related Question

For a set $A \subseteq \omega$, let $[A]^n$ denote the set of subsets of $A$ of size $n$. I am trying to prove Ramsey's Theorem, and it seems like the following fact is used in the proof I am reading ...
6
votes
1answer
588 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 ...
1
vote
1answer
125 views

Strengthened finite Ramsey theorem

I'm reading wikipedia article about Paris-Harrington theorem, which uses strengthened finite Ramsey theorem, which is stated as "For any positive integers $n, k, m$ we can find $N$ with the following ...
7
votes
1answer
676 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 ...
2
votes
1answer
295 views

Algorithm to find a permutation that contains the fewest possible monotone subsequences of length $k$

Fix natural numbers $k,n$, with $k<n$. I want to find a permutation in $S_n$ that contains fewest monotone (increasing or decreasing) subsequences of length $k$. For example the permutation ...
7
votes
1answer
278 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 ...
3
votes
2answers
444 views

Lower bound for monochromatic triangles in $K_n$

Say $K_n$ is a complete graph of $n$ nodes, and every edge is either blue or red. I'm trying to find $T_n$, which is the lower bound for the number of monochromatic triangles in $K_n$ (monochromatic ...
3
votes
1answer
503 views

How to prove this relation between Ramsey Numbers: $R(s, t) ≤ R(s, t-1) + R(s-1, t)$ for $s,t>2$

I am trying to prove that $$R(s, t) ≤ R(s, t-1) + R(s-1, t) $$ for $s,t>2$, where $R(s,t)$ is the Ramsey number of $(s,t)$, and I'd be really grateful for a hint that gets me started.
4
votes
1answer
367 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 ...
3
votes
1answer
172 views

Extended form of infinite Ramsey's Theorem

I'm working on some Combinatorics, and in the past have happily used the infinite Ramsey Theorem (as detailed on http://en.wikipedia.org/wiki/Ramsey%27s_theorem), which says that for something like ...
5
votes
1answer
297 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 ...
6
votes
2answers
238 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 ...
5
votes
1answer
263 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 ...
7
votes
1answer
230 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 ...
4
votes
1answer
132 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 ...
6
votes
1answer
314 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 ...
3
votes
1answer
182 views

A “geometrical” representation for Ramsey's theorem

The [infinite] Ramsey theorem states that Let $n$ and $k$ be natural numbers. Every partition $\{X_1,\ldots ,X_k\}$ of $[\omega]^n$ into $k$ pieces has an infinite homogeneous set. Equivalently, ...
4
votes
2answers
490 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 ...