On Ramsey-type problems for sequences and permutations

Graphs, Hypergraphs, and Computing

10 April 14:00 - 15:00

Andrzej Dudek - Western Michigan University

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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to