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
Adam Mickiewicz University
Technical University of Denmark, DTU