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.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456