---
jupytext:
  cell_metadata_filter: -all
  formats: md:myst
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.10.3
kernelspec:
  display_name: SageMath
  language: sage
  name: sagemath
---
# 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 
 {cite}`Duffin1959` [(pdf)](https://www.ams.org/journals/tran/1959-093-01/S0002-9947-1959-0109161-6/S0002-9947-1959-0109161-6.pdf)
and Wai-Kai Chen {cite}`Chen1966directed` [(pdf)](https://epubs.siam.org/doi/pdf/10.1137/0114048)---and my research interest in the biophysical theory of receptor oligomers {cite}`HammackSmith17,ConradiSmith2020` [(pdf)](https://amc-journal.eu/index.php/amc/article/view/856).

## Co-spanning trees from cycle basis

In ref. {cite}`Duffin1959`, 
Richard Duffin  states that a commutative algebra with the property that 

```{math}
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 {cite}`Duffin1959,Duffin1974`.  A similar method involves obtaining directed spanning trees from the stars of G centered on each vertex save an arbitrary root {cite}`Chen1966directed`.    I will focus on the undirected case, because I wish to use the minimal cycle basis construction for reduced graph powers {cite}`HammackSmith2017`. 

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

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

```{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 {math}`K_4`, the complete graph of four vertices.
The polynomials in the Wang algebra corresponding to the cycle basis {math}`\mathcal{C}(K_4)` are `{adf, bde, cef}` OR {math}`\{adf, bde, cef\}`. Thus, 

```{math}
h_1 = a + d +f \quad h_2 = b+d+e \quad h_3 = c+e+f \, . 
```

The product {math}`h_1h_2` is

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

Multiplying by {math}`h_3` gives

```{math}
\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}
```

which is {math}`18-2=16` terms because `def+def=0`.  Each surviving term of {math}`h_1 h_2 h_3` corresponds to a co-tree of {math}`K_4` (e.g., the co-tree `abc` corresponds to the spanning tree `def`).  Note that {math}`\binom{abcdef}{3}` corresponds total of 20 possible triples, all of which are co-trees of {math}`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 

```{bibliography}
:filter: docname in docnames
```