Subgraphs versus Orientations: Infinite families of equidistributions

Abstract

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. Namely, given two sets of pairs of vertices $A=\{(u_i,v_i),i\in [k]\}$ and $B=\{(u_i^{\prime },v_i^{\prime }),i\in [l]\}$, we consider the orientations $\alpha$ of $G$ such that adding the elements of $A$ and $B$ as additional directed edges to $\alpha$ gives an orientation ${\alpha }^{\prime }$ in which $v_i$ cannot reach $u_i$ for all $i\in [k]$, but $v_i^{\prime }$ can reach $u_i^{\prime }$ for all $i\in [l]$. We show that this set of orientations is equinumerous to a set of subgraphs satisfying the ``same" connectivity constraints defined in terms of $A$ and $B$. We also extend our results to the enumeration of equivalence classes of orientations satisfying such connectivity constraints. Precisely, we consider the equivalence classes under cycle reversal, cocycle reversal, or cycle-cocycle reversal. We show that the equivalences classes are equinumerous to some sets of subgraphs defined by connectivity and acyclicity constraints.