On July 29, 2025, Colin Geniet from the IBS Discrete Mathematics Group gave a talk on the merge-width of graphs and 𝜒-boundedness of graphs of bounded merge-width at the Discrete Math Seminar. The title of his talk was “merge-width“.
Colin Geniet, Merge-width
This talk is an introduction to the recent notion of merge-width, proposed by Jan Dreier and Szymon Torúnczyk. I will give an overview of the context and motivations for merge-width, namely the first-order model checking problem, and present the definition, some examples, and some basic proof techniques with the example of χ-boundedness.
This is based on joint work with Marthe Bonamy.
Colin Geniet gave a talk at the Discrete Math Seminar on characterizing classes of permutations avoiding a fixed pattern
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“.
Colin Geniet, 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é.
Welcome Colin Geniet, a new member of the IBS Discrete Mathematics Group
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.