## Graphical Supersymmetry Algebras

Thanks to Dr. James Hughes, Matthew Lynn, Chris Walker, Chas Leichner, Alex Ray, Alex Zhu, Dr. Cornelia Van Cott, Paul Sebexen, Colin Aitken, Chuck Moulton, Sebastien Zany, and Nick for joining me in playing with this problem.

Adinkras are colored connected simple graphs, that are bipartite and n-regular.

Adinkras are a graphical representation of supersymmetry algebras.

The prefix super- comes from the theory of supersymmetry in theoretical physics. Superalgebras and their representations, supermodules, provide an algebraic framework for formulating supersymmetry.

A superalgebra is a $\mathbb{Z}_2$-graded algebra. In other words, it is “an algebra over a commutative ring or field with decomposition into ‘even’ or ‘odd’ pieces and a multiplication operator that respects the grading.”

#### What is an odd adinkra?

An adinkra is odd if the sum of every 4-cycle in the adinkra is odd.

To create an odd adinkra: we assign 0 or 1 to every edge of an n-dimensional cube such that, for each face of the cube, the sum of the edges of the face is odd.

#### How many unique n-dimensional odd adinkras exist?

Before we attack this, let’s elaborate on the problem:

First some notation must be fixed. By $E(G)$, we mean the edges of the graph $G$, and by $Q_n$, we mean the graph corresponding to the $n$-dimensional cube. The formal statement is then as follows.

How many edge 2-colourings $\phi : E(Q_n) \to \{0,1\}$ exist such that, for each 4-cycle $C$ of $Q_n$, the sum of the edge colours is odd: $\sum_{e \in E(C)} \phi(e) = 1$ mod $2$ ?

Note that we bastardize the term “edge n-colourings” $\equiv$ assignment of $x \in {0,1,..,n-1}$ to every edge.

#### Breaking Down The Problem: The Overture

Let $e_n$ denote the number of edge colourings of $Q_n$ for which the sum of the edge colours is even, and let $o_n$ denote the number of edge colourings for which the sum is odd. As $Q_0$ contains a single vertex and no edges, there are no edge colourings with either property, so we set $e_0 = o_0 = 1$.

Now $Q_1$ contains two vertices with a single edge between them, so $e_1 = o_1 = 1$. The slightly more interesting graph $Q_2$ corresponds to a square, which can have its edges 2-coloured in $2^4$ ways. Half of which will correspond to an even sum, the other half to an odd, so $e_2 = o_2 = 8$. The graph $Q_3$ can be 2-coloured in $2^{12}$ ways, half of which must be even and the other half odd, so $e_3 = o_3 = 2^{11}$.

Conjecture: For all $n$, $e_n = o_n = 2^{|E(Q_n)| – 1}$.

When constructing $Q_{n+1}$ from $Q_n$ we are duplicating the graph $Q_n$ and connecting every vertex of the duplicate to the original.

#### Combinatorial Approach

For a 2-cube: we have 2 different states [the sides sum to 1 or 3], and 4 unique rotational variants of each state. $2*4 =8$

Can we write this in a closed form? The set of all unique states of the cube is $2^8$.

We have 8 different choosing points, one for each of the 8 edges.
For each of these choosing points, we have 2 different options: pick 0 or 1.

For the front face of the cube, we have $2^{2^{n-1}-1}$

For the back face of the cube, we also have $2^{2^{n-1}-1}$

The state of this edge is completely determined by this edge [following an intuition we will confirm in the following section]. Therefore, instead of adding 4 more options, we only add 2.

This gives us $2^{2^{(n−1)}} \cdot 2^{2^{(n+1)}} \cdot 2^1 = 2^{2^n-1}$. $_\blacksquare$

#### Visually Formalizing our Intuition

Until we prove our hunch is correct, there is a hole in the induction step where one would need to show that many ways to glue to n-1 dimensional hypercubes together exist.

Intuitively, as soon as you fill in 1 edge (0 or 1) that fixes the rest of them $\rightarrow$ meaning that there are only 2 valid ways to connect any 2 $n$-dimensional cubes into a ($n+1$)-dimensional cube.

This can be visually formalized and inductively proven:

We can add the corresponding edges of the (n-1)-cubes to get a new (n-1) cube, and then the old problem of coloring the edges between the two cubes becomes the problem of coloring vertices so that the sum of the colors of two vertices is the same as the number on the edge between them.

#### Computational Attacks

All code used in this post is on my github.

generate_hypercube.py

The set-theoretic approach is just a cool way to think about graph generation.

# Hypercube Problem

from itertools import chain, combinations

# Create generator set for hypercube of dimension x
def S(x):
return set(range(0,x))

# From http://stackoverflow.com/questions/18035595/powersets-in-python-using-itertools
def powerset(iterable):
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

# Generate a list of edges given a list of vertices
def edges(verts):
return set(frozenset([x, y]) for x in verts for y in verts if len(x ^ y) == 1)

# Run this to generate hypercube of specified number of dimensions
def Qgen(dimensions):
genSet = S(dimensions)
print(genSet)
Verts = list(powerset(genSet))
print(Verts)
sVerts = set(frozenset(x) for x in Verts)
print(sVerts)
print(len(sVerts))
Edges = edges(sVerts)
print(Edges)
print(len(Edges))
return

cube.py

Shiny Graphviz to generate n-dimensional Hamming cubes which falls apart around n=8.

import colorsys
import itertools
import sys

n = int(sys.argv[1])
bits = list(itertools.product([0, 1], repeat=n))

HSV_tuples = [(x*1.0/n, 0.5, 0.5) for x in range(n+1)]
tuples = map(lambda x: '#%02x%02x%02x' % tuple(map(lambda x: int(x*255), colorsys.hsv_to_rgb(*x))), HSV_tuples)

def diff(a, b):
difference = 0
for a0, b0 in zip(a, b):
difference += a0 != b0
return difference

def reprtag(t):
return "".join(str(b) for b in t)

print 'graph cube {'
print '  ranksep=', n/2.0, ';'
print '  fontsize=8;'
seen = set()
for ((a, b), c) in zip(itertools.product(bits, bits), itertools.cycle(tuples)):
if diff(a, b) == 1 and (b, a) not in seen:
print '  "', reprtag(a), '"',  '--', '"', reprtag(b), '" [color="',  c, '"]'
print '}'


Dependency:

sudo apt-get install graphviz

Make them all in one go:

Credit: Alex Ray

#### Conclusion

You know those problems which you know you shouldn’t be thinking about but keep bugging you so you occasionally work on them in desperation and then forcibly shove them to the backburner?

This is one of those problems. We’ve conquered it.