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
3answers
636 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
133 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
227 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
574 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
122 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
597 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
284 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
273 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
426 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
491 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
366 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
166 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
294 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
237 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
261 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
227 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
129 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
307 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 ...
2
votes
1answer
178 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
477 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 ...