Combinatorics Seminar - Jean Cardinal


Speaker: Jean Cardinal

Title: Diameter estimates for graph associahedra

Abstract: 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 treedepth 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.