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

11
votes
2answers
417 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 ...
6
votes
1answer
322 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 ...
12
votes
1answer
772 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
2answers
195 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
110 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 ...
3
votes
2answers
463 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$ ...
1
vote
1answer
148 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 ...
3
votes
1answer
55 views

Verify that R(p,2) = R(2,p) = p, where R is the Ramsey number

Verify that $R(p,2) = R(2,p) = p$, where $R$ is the Ramsey number It just seems obvious that $R(p,2) = R(2,p)$. But why do $R(p,2)$ and $R(2,p)$ both equal p?
3
votes
1answer
267 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
1answer
184 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, ...
1
vote
1answer
123 views

Girth and monochromatic copy of trees

Question: Prove that for every tree $T$ and every integer $g$ there exists a graph $G$ without cycles of length up to $g$ and such that every two-coloring of the edges of $G$ contains a monochromatic ...
0
votes
0answers
18 views

Question about a possible relationship between additive and Bergelson multiplicative upper densities

Let $A \subseteq \mathbb{N}$; let $\mathbb{P} \subset \mathbb{N}$ be the set of all primes. Let $\forall n \in \mathbb{N}, F_n = \{a_n \prod_{i=1}^n (p_i^{r_i}): a_n \in \mathbb{N}, p_i \in ...
7
votes
2answers
144 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
5
votes
1answer
67 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$ ...
6
votes
3answers
914 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
2answers
126 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
0answers
199 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 ...
4
votes
1answer
121 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
2answers
207 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 ...
3
votes
1answer
203 views

Accessible Applications of Graph Ramsey Theory

I am giving a short lecture series on graph Ramsey theory to a group of gifted high school seniors. The brief outline is to start with the "six people at a dinner party" question, transition into the ...
2
votes
2answers
131 views

How can we apply Ramsey's theorem to solve this problem on matrices?

This is from a problem set in a combinatorics course I am taking, and reads as follows: Let $m\geqslant 1$ be an integer. Prove there exists an $n\geqslant 1$ with he following property: every ...
4
votes
2answers
419 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 ...
2
votes
1answer
139 views

A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I'm following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an ...
2
votes
2answers
124 views

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and ...
2
votes
3answers
78 views

Is there only one counter example in $K_5$ for $R(3,3)$?

Title says it all. And the one that I know is below. (image from wikipedia) My question is: Is there only one counter example in $K_5$ for $R(3,3)$ where $K_5$ is a complete graph of 5 points and ...
2
votes
1answer
210 views

Ramsey Number proof

I am trying to prove: $R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$ I am confused as to how one can go from a $4$ color problem to a $3$ color problem by multiplying and adding. edit: $R$ is the Ramsey ...
1
vote
0answers
58 views

Find n that satisfies the following [duplicate]

Find the smallest positive integer n that satisfies the following: We can color each positive integer with one of n colors such that the equation w + 6x = 2y + 3z has no solutions in positive integers ...
1
vote
1answer
102 views

$K_6$ contains at least two monochromatic $K_3$ graphs.

Let $K_n$ be a complete $n$ graph with a color set $c$ with $c=\{\text{Red}, \text{Blue}\}$. Every edge of the complete $n$ graph is colored either $\text{Red}$ or $\text{Blue}$. Since $R(3, 3)=6$, ...
0
votes
1answer
61 views

combinatorics- persons in group

Let $$ n = \binom {k + b-2}{k-1} \text{ and }k, b\ge 2 $$ Prove that in each group of at least n persons there is k person is familiar with everybody or there are b persons two did not know each ...