Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 10, 2022, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Jean Cardinal (Université Libre de Bruxelles)
Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph G encodes the combinatorics of search trees on G, defined recursively by a root r together with search trees on each of the connected components of G−r. In particular, the skeleton of the graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters such as tree-depth and treewidth, and give tight estimates for specific families of graphs, including trivially perfect, complete split and complete bipartite graphs. This is a joint work with Lionel Pournin and Mario Valencia-Pabon from Université Sorbonne Paris Nord.
Automatic MiSe System Software Version 1.4803M | admin login