Subgraphs versus Orientations: Infinite families of equidistributions

A classical enumerative result states that, given a graph G and a vertex u, the number of connected subgraphs of G is equal to the number of orientations of G such that every vertex can reach u by a directed path. We show that this result is an instance of a much broader set of enumerative identities between subgraphs and orientations corresponding to various connectivity constraints. This is joint work with Jonathan Fang.

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