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

1
vote
0answers
116 views

What was done to calculate the Ramsey numbers using a quantum computer?

I recently came across this paper titled Experimental determination of Ramsey numbers with quantum annealing I was wondering what exactly the gist of the paper, as I read it, it seems rather ...
2
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
4answers
209 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$ ...
5
votes
1answer
928 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}$ ...
6
votes
0answers
157 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: ...
2
votes
1answer
170 views

Coloring Vertices of a 50-gon

This is a problem that I have spent a good 2 hours on but can seem to come up with any rigorous solution. If someone could provide one that would be great! If we color 21 vertices of a 50-gon, how do ...
2
votes
0answers
75 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 ...
1
vote
1answer
125 views

Best known bounds for Ramsey numbers

I realize a similar question has been asked before but what I want to know is a little different and is not answered by the link in the answer to that question. I am interested in knowing the best ...
2
votes
1answer
79 views

2012-gon- subsets of vertices.

Can we prove or disprove this? For a sufficiently large $n$, every set of at least $ n$ points in the plane with no three collinear has a subset that form the vertices of a convex $2012$-gon. Gerry ...
0
votes
2answers
90 views

Complete graph-coloring

Can we prove or disprove the following statement? For any graph $H$ and any coloring $c$ of its edges with two colors, there exists $n$ such that every $2$-coloring of the edges of the complete graph ...
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 ...
7
votes
0answers
209 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 !
4
votes
1answer
114 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
3answers
164 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 ...
2
votes
0answers
71 views

Monochromatic degenerate triangles in a two-coloring of the plane

In a similar vein to a question I asked a few days ago: Do all two-colorings of $\mathbb{R}^2$ contain three points of the same color which form the vertices of a degenerate triangle of side-lengths ...
3
votes
1answer
275 views

Gallai's theorem, colourings and equivalence relations

I'm revising a few past papers on Ramsey theory and I've come across a question which feels like it should be easy if it weren't so confusingly set up - I was hoping someone here could help me make ...
6
votes
1answer
163 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 ...
1
vote
2answers
761 views

Ramsey Number R(4,4)

In trying to deduce the lower bound of the ramsey number R(4,4) I am following my book's hint and considering the graph with vertex set $\mathbb{Z}_{17}$ in which $\{i,j\}$ is colored red if and only ...
6
votes
2answers
442 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
164 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
99 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
86 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
541 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
125 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
207 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 ...
5
votes
1answer
510 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
104 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
496 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
250 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
249 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
363 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
427 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
347 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
151 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
272 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
234 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
234 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
214 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
125 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
281 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
172 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
421 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 adjacency ...