6
votes
2answers
97 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 ...
2
votes
1answer
236 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 ...
5
votes
1answer
220 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 ...