기초과학연구원 이산수학그룹
On June 13, 2022, Amadeus Reinald from the ENS de Lyon and the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar, proving that graphs of girth at least 5 without an induced subdivision of $K_{2,3}$ have bounded twin-width. The title of his talk was “Twin-width and forbidden subdivisions“.
Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, problems expressible in FO logic can be solved in FPT time when provided with a sequence witnessing the bound. Classes of bounded twin-width are very diverse, notably including bounded rank-width, $\Omega ( \log (n) )$-subdivisions of graphs of size $n$, and proper minor closed classes. In this talk, we look at developing a structural understanding of twin-width in terms of induced subdivisions.
Structural characterizations of graph parameters have mostly looked at graph minors, for instance, bounded tree-width graphs are exactly those forbidding a large wall minor. An analogue in terms of induced subgraphs could be that, for sparse graphs, large treewidth implies the existence of an induced subdivision of a large wall. However, Sintiari and Trotignon have ruled out such a characterization by showing the existence of graphs with arbitrarily large girth avoiding any induced subdivision of a theta ($K_{2,3}$). Abrishami, Chudnovsky, Hajebi and Spirkl have recently shown that such (theta, triangle)-free classes have nevertheless logarithmic treewidth.
After an introduction to twin-width and its ties to vertex orderings, we show that theta-free graphs of girth at least 5 have bounded twin-width.
Joint work with Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant.
The IBS Discrete Mathematics Group welcomes Amadeus Reinald, a visiting graduate student from the ENS de Lyon in France. He is planning to stay with us until August 26, 2022.