## You are here

Bijections between subgraphs and orientations of a graph and Lawrence polytopes

Bijections between subgraphs and orientations of a graph and Lawrence polytopes

We unify the Bernardi bijection (restricted to spanning trees) and the geometric bijection in the same framework so that they are two special cases, behind which dissections of Lawrence polytopes play a key role.

Fix a graph $G$. Backman, Baker, and Yuen constructed a bijection between the spanning trees of $G$ and the equivalence classes of orientations of $G$ up to cycle-cocycle reversal. Earlier Bernardi constructed a bijection between the spanning subgraphs and the orientations of $G$. If we restrict the Bernardi bijection to trees, it will also be bijective to the equivalence classes of orientations up to cycle-cocycle reversal. One common feature of their bijections is that, given a tree, they orient the edges in the tree and the edges not in the tree separately.

We consider the Lawrence polytopes $P$ and $P^*$ associated to the graphic matroid $M(G)$ and the cographic matroid $M^*(G)$, respectively. We construct a map from the spanning trees to the orientations of $G$ where for every tree the edges not in the tree are oriented by a dissection of the Lawrence polytope $P$ and the edges in the tree are oriented by a dissection of $P^*$. According to this construction, the geometric bijection is induced by a pair of (regular) triangulations, and the Bernardi bijection is induced by a dissection of $P$ (due to Kalman and Tothmeresz) and a triangulation of $P^*$. In general, if one of the two dissections is triangular, the induced map is bijective to the equivalence classes of orientations up to cycle-cocycle reversal. Moreover, the bijection can be extended to a subgraph-orientation correspondence.

## Department of Mathematics and Statistics