Compatibility fans for graphical nested complexes

摘要

Graph associahedra generalize classical associahedra. They realize the nested complex of a graph G, i.e. the simplicial complex whose vertices are the tubes (connected induced sub graphs) of G and whose faces are the tubings (collections of pairwise nested or non-adjacent tubes) of G. The constructions of M. Carr and S. Devadoss, of A. Postnikov, and of A. Zelevinsky for graph associahedra are all based on the nested fan, which coarsens the normal fan of the permutahedron. In view of the variety of fan realizations of associahedra, it is tempting to look for alternative fans realizing graphical nested complexes. Motivated by the analogy between finite type cluster complexes and graphical nested complexes, we transpose S. Fomin and A. Zelevinsky's compatibility fans from the former to the latter setting. We define a compatibility degree between two tubes of a graph G and show that the compatibility vectors of all tubes of G with respect to an arbitrary maximal tubing on G support a fan realizing the nested complex of G. When G is a path, we recover F. Santos' Catalan many realizations of the associahedron. (C) 2017 Elsevier Inc. All rights reserved.