기초과학연구원 이산수학그룹
On October 22, 2024, Colin Geniet from the IBS Discrete Mathematics Group gave a talk on characterizing classes of permutations avoiding a fixed pattern at the Discrete Math Seminar. The title of his talk was “Permutations, patterns, and twin-width“.
This talk will first introduce combinatorics on permutations and patterns, presenting the basic notions and some fundamental results: the Marcus-Tardos theorem which bounds the density of matrices avoiding a given pattern, and the Guillemot-Marx algorithm for pattern detection using the notion now known as twin-width.
I will then present a decomposition result: permutations avoiding a pattern factor into bounded products of separable permutations. This can be rephrased in terms of twin-width: permutation with bounded twin-width are build from a bounded product of permutations of twin-width 0. Comparable results on graph encodings follow from this factorisation.
This is joint work with Édouard Bonnet, Romain Bourneuf, and Stéphan Thomassé.
The IBS discrete mathematics group welcomes Dr. Colin Geniet, a new research fellow at the IBS Discrete Mathematics Group from September 1, 2024. He received his Ph.D. from ENS de Lyon under the supervision of Prof. Stéphan Thomassé. He is interested in graphs in relation with logic and algorithmic, and more specifically structural graph theory, graph parameters, finite model theory, and parameterized complexity.