9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

Splittable Permutation Classes

Presented by Vít JELíNEK
Type: Oral presentation
Track: Combinatorics

Content

We say that a permutation p is `merged' from permutations q and r, if we can color the elements of p red and blue so that the red elements are order-isomorphic to q and the blue ones to r. With Claesson and Steingr{\'\i}msson, we have shown, as a special case of more general results, that every permutation that avoids the subpermutation 1324 can be merged from a permutation that avoids 132 and a permutation that avoids 213. This is a simple example of a property called splittability: we say that a hereditary permutation class C is `splittable', if it has two proper hereditary subclasses A and B such that any element of C can be obtained by merging an element of A with an element of B. In my talk, I will show how splittability helps in enumeration of restricted permutations, explain how splittability relates to other Ramsey-type properties, and point out a close connection between splittability of certain permutation classes and the notion of $\chi$-boundedness of circle graphs. I will then report on the recent progress in identifying which principal permutation classes are splittable.

Place

Location: Koper, Slovenia

Primary authors

  • Vít JELíNEK Computer Science Institute, Charles University, Prague
More