Wang algebra

In classical electrical network theory, algebraic approaches to enumerating spanning trees of graphs were popular. This chapter of notes focuses on connections between one technique for enumerating tree and cotrees—referred to in the 1960s as a Wang algebra by Richard Duffin [Duf59] (pdf) and Wai-Kai Chen [Che66] (pdf)—and my research interest in the biophysical theory of receptor oligomers [CS20] (pdf).

Co-spanning trees from cycle basis

In ref. [Duf59], Richard Duffin states that a commutative algebra with the property that

\[x+x = 0 \quad \mbox{and} \quad x\cdot x = 0 \]

for each element $x$ is termed a Wang algebra. Classical electrical network theory discusses using Wang algebra’s to obtain co-spanning trees of an undirected simple graph G from a cycle basis [Duf59, Duf74]. A similar method involves obtaining directed spanning trees from the stars of G centered on each vertex save an arbitrary root [Che66]. I will focus on the undirected case, because I wish to use the minimal cycle basis construction for reduced graph powers [HS17].

Let \(G = (V,E)\) be an undirected simple graph of order \(|V|=m\) and size \(|E|=n\) with \(V(G)= \{ v_1, v_2, \ldots, v_m \}\) and \(E(G) = \{ e_1 , e_2, \ldots , e_n\}\). For \(1\leq i \leq n\) let \(x_i\) be an indeterminant corresponding to edge \(e_i\) of \(G\). Let \(R=\mathbb{F}_2[x_1, x_2, \ldots, x_n]\) be a polynomial ring over the field \(\mathbb{F}_2\). Define \(S\) to be the quotient ring

\[S = R/I \quad \mbox{where the ideal} \quad I = \langle x_1^2, x_2^2, \ldots, x_n^2 \rangle \]

generated by squares of indeterminants.

If \(C_1,C_2,\ldots,C_\beta\) are \(\beta\) independent circuits of \(G\), and \(h_{i} = \sum_{j: e_j \in C_i} x_j\) are polynomials in \(S\) corresponding to these circuits, then the co-trees (spanning tree complements) of $G$ correspond to the surviving monomials of the product \(\Phi^*_G(x_1, \ldots, x_n) = h_{C_1} h_{C_2} \cdots h_{C_\beta}\), which is dual to
the Kirchhoff polynomial \(\Phi_G\). This fact is attributed to Wang and Ting in [Che66].

Note

The Wang algebra is isomorphic to a Grassmann (exterior) algebra over the field $\mathbb{F}2$.

Example: Co-spanning trees of $K_4$

Consider \(K_4\), the complete graph of four vertices. The polynomials in the Wang algebra corresponding to the cycle basis \(\mathcal{C}(K_4)\) are {adf, bde, cef} OR \(\{adf, bde, cef\}\). Thus,

\[h_1 = a + d +f \quad h_2 = b+d+e \quad h_3 = c+e+f \, . \]

The product \(h_1h_2\) is

\[h_1 h_2 = \mathrm{ab}+ad+ae+bd+0+de+bf+df+\mathrm{ef} \, .\]

Multiplying by \(h_3\) gives

\[\begin{split}\begin{eqnarray} h_1 h_2 h_3 &=& abc + acd + ace+bcd+cde+bcf+cdf+cef \nonumber \\ &+ &abe + ade + 0+bde+0+bef+[def]+0 \nonumber \\ &+& abf + adf + aef+bdf+[def]+0+0+0 \, , \nonumber \end{eqnarray}\end{split}\]

which is \(18-2=16\) terms because def+def=0. Each surviving term of \(h_1 h_2 h_3\) corresponds to a co-tree of \(K_4\) (e.g., the co-tree abc corresponds to the spanning tree def). Note that \(\binom{abcdef}{3}\) corresponds total of 20 possible triples, all of which are co-trees of \(K_4\) except abd, acf, bce and def$.

Note

I haven’t been able to get latex definitions such as \def\a{\mathsf{a}} to work. That is why I am experimenting with \mathrm and \!f above.

References

[Che66] (1,2,3)

Wai-Kai Chen. On directed trees and directed k-trees of a digraph and their generation. SIAM Journal on Applied Mathematics, 14(3):550–560, 1966.

[CS20]

Gregory Douglas Conradi Smith. Allostery in oligomeric receptor models. Mathematical Medicine and Biology, 37:313–333, 2020.

[Duf59] (1,2,3)

R J Duffin. An analysis of the Wang algebra of networks. Transactions of the American Mathematical Society, 93(1):114–131, 1959.

[Duf74]

RJ Duffin. Some problems of mathematics and science. Bulletin of the American Mathematical Society, 80(6):1053–1070, 1974.

[HS17]

RH Hammack and GD Smith. Cycle bases of reduced powers of graphs. ARS Mathematica Contemporanea, 12(1):183–203, 2017.