Tutte seminar - Gelasio Salazar

Some of the most natural and basic questions in Combinatorics can be posed as problems on (decompositions of) permutations. For instance: given a permutation, how can it be efficiently decomposed into (many) subpermutations with certain properties? Or, given several permutations: which are the longest subpermutations (or subpatterns) that they have in common? In this talk we’ll review some of these problems, and explore their relationship to another hard combinatorial problem: how to embed a graph into a book with ”few” pages. This is joint work with Jozsef Balogh.