Séminaire Lotharingien de Combinatoire, 91B.101 (2024), 12 pp.
William T. Dugan
On The f-Vectors of Flow Polytopes for The Complete Graph
Abstract.
The Chan-Robbins-Yuen polytope (CRYn) of order n is a face of the Birkhoff polytope of doubly stochastic matrices that is also a flow polytope of the directed complete graph Kn+1 with netflow (1,0,0,...,0,-1). The volume and lattice points of this polytope have been actively studied, however its face structure has received less attention. We give generating functions and explicit formulas for computing the f-vector by using Hille's (2003) result bijecting faces of a flow polytope to certain graphs, as well as Andresen and Kjeldsen's (1976) result that enumerates certain subgraphs of the directed complete graph. We extend our results to flow polytopes over the complete graph having arbitrary (non-negative) netflow vectors and recover the f-vector of the Tesler polytope of Mészáros, Morales and Rhoades (2017).
Received: November 15, 2023.
Accepted: February 15, 2024.
Final version: April 1, 2024.
The following versions are available: