On the f-vector of flow polytopes for complete graphs

The Chan-Robbins-Yuen polytope (CRY_n) of order n is aface of the Birkhoff polytope of doubly stochastic matrices that isalso a flow polytope of the directed complete graph K_{n+1} withnetflow (1,0,0, … , 0, -1). The volume and lattice points ofthis polytope have been actively studied, however its face structurehas been studied less. We give explicit formulas and generatingfunctions for the f-vector of CRY_n by using Hille’s (2007) resultbijecting faces of a flow polytope to certain graphs, as well asAndresen-Kjeldsen’s (1976) result that enumerates certain subgraphs ofthe directed complete graph. We extend our results to flow polytopesover the complete graph having arbitrary (non-negative) netflowvectors and study the face lattice of CRY_n.

For information about the Richard P. Stanley Seminar in Combinatorics, visit https://math.mit.edu/combin/