Combinatorics Seminar: The Maximal Tubings of the Cycle Graph and G-inversions

Abstract: A Maximal tubing of a graph G is a set of connected subgraphs of G that satisfy certain compatibility criteria. The collection of all maximal tubings MTub(G) has with a natural partial order that generalizes several well-known and well-studied partial orders. For example, if G is the complete graph Kn, then this poset MTub(Kn) is isomorphic to the weak Bruhat order on permutations, and if G is a path graph Pn, then MTub(Pn) forms the Tamari Lattice. This talk considers maximal tubings on the cycle graph Cn, where MTub(Cn) is an order on the vertices of a polytope called the cyclohedron. While Mtub(Cn) is conjectured to be a lattice, in contrast to MTub(Kn) and MTub(Pn), very little is known about this order other than its cover relations. In this talk, we show how maximal tubings of the cyclohedron can be characterized by a special type of tree called “cyclic binary trees”, and use properties of those cyclic binary trees to fully describe the global order relations on MTub(Cn).

This is primarily joint work with Bryson Kagy, in part of a larger collaboration stemming from an AMS MRC project with Ben Adenbaum, Emily Barnard, Max Hlavacek, George Nasr, Katherine Ormeño Bastías, and Katie Waddle. 

Host: Martha Precup