The Setting
Let and be finite networks with vertex sets and , respectively, and a common edge set .
A network on a vertex set is a directed multigraph assigning a tail and a head in to every edge.✦ The underlying simple graph of a network is the graph on its vertex set that joins distinct vertices whenever an edge of has those endpoints, in either order.✦ A simple network is a network with no loops and at most one edge with any given unordered pair of endpoints.✦ An edge of a network is incident with a vertex of when is the tail or the head of .✦ The star of a vertex in a network is the set of all edges incident with .✦
The oriented incidence matrix of a network is the matrix with entries given by (1), where is when holds and otherwise. (1)✦ The boundary operator of a network is the linear map that sends real edge weights to their signed net inflows at vertices.✦ The gradient operator of a network is the linear map that sends a real vertex potential to its differences across edges.✦ These linear maps are given by (2). (2)
A cycle-cut duality between networks and is an identification of their real cycle and cut spaces as in (3), with both underlying graphs connected. (3)✦
Put . A triangle of a network on an edge set is a pair of families of distinct corners and distinct edges , indexed by , such that the edges exhaust and joins to .✦ For an edge and a vertex of a network , the outgoing edge sign is the number when is the tail of and otherwise.✦
A colored triangulation duality between and is a cycle-cut duality in which both networks are simple and is cubic, together with a black class giving a bipartite coloring. Each has a dual triangle with corners and sides whose side set is . The orientation compatibility of these triangles is (4), where is the potential equal to at and elsewhere. (4)
The Claim
Definition 1. Fix a black root triangle , identified with its vertex in . The nonroot black triangles form the set ✦, and the nonroot dual vertices form the set , defined by (5). (5)
A triangle system on a vertex set , indexed by a set , is a family of three distinct vertices for each triangle, with no two different triangles sharing two vertices.✦ Its corner map satisfies (6). (6)✦
A state of on a set is a corner choice whose selected vertices give a bijection onto , as in (7).✦ Write for the selected vertex of triangle , and for the set of states. (7)✦
Two states are partners, written , when they make distinct selections at every triangle, as specified in (8). (8)✦
A paired state of on is an ordered pair of partner states of on .✦ The set of paired states of on is given by (9). (9)✦
What Is Checked
The state and partner definitions apply to any triangle system and any subset of its vertex set; the rooted sets arise from a finite colored triangulation duality with a black root.