Andrzej Dudek: On Ramsey-type problems for sequences and permutations

Ramsey theory can loosely be described as the study of structure which is preserved under finite decomposition. A classical Ramsey theorem states that in any r-coloring of the edges of a sufficiently large complete graph, one will always find a monochromatic complete subgraph.

In this talk, we discuss analogous results for sequences and permutations. In particular, we study the behavior of the following function f(r,X), which is the length of the shortest sequence Y such that any r-coloring of the entries of Y yields a monochromatic subsequence that also preserves the order of X.