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

10
votes
2answers
273 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
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 ...
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.
3
votes
2answers
283 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
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 ...
3
votes
1answer
211 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$ ...
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, ...
7
votes
2answers
133 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
3answers
567 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
101 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 ...
4
votes
1answer
103 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
138 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 ...
2
votes
1answer
152 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 ...
4
votes
2answers
303 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
175 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
1answer
67 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
0answers
66 views

How prove this will be a length of $3$ arithmetic progression. [duplicate]

This problem is my frend give me: Given $122$ consecutive integers, show that randomly selected $33$ integer, of which there will be a length of $3$ arithmetic progression. hint: length of ...