Cubelike Graphs

A cubelike graph is a Cayley graph for $\ints_2^d$. The connection set of such a graph can be encoded by a $d\times m$ matrix with distinct columns. If $M$ is such a matrix then we can get a list of its columns with cols = M.columns() and we can recover $M$ with M = Matrix(cols).transpose().

The natural choice for the vertices of a cubelike graph are the elements of

V = VectorSpace( GF(2)), d)  # not tested

but these are not hashable. We can make a vector v hashable with v.set_immutable() and use vectors as vertices, or work as follows. Suppose that vls is a list of vectors from a vector space V.

G = Graph( [[0..len(vls)-1],\
    lambda i,j: vls[i]-vls[j] in V.list()]) # not tested
P = graphs.PetersenGraph()
D = P.incidence_matrix()
B = D.change_ring( GF(2))  # convert to a matrix over GF(2)
B0 = B.submatrix( nrows=B.nrows()-1)  # delete last row
B0
[1 1 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 1 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 1 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 1 1 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 1 1 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 0 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 1 0 0 1 0]

For humans it can be convenient to encode binary vectors of length $d$ as integers between 0 and $2^{d-1}$. With $G$ as just defined, its connection set will be the correct set of integers.

def cubelike(vecls):
    d = len(vecls[0])
    VS = VectorSpace(GF(2),d)
    return Graph([[0..(2^d-1)], lambda i,j: VS[i]-VS[j] in vecls])
PP = cubelike(B0.columns())
PP.am().fcp()
(x - 15) * (x + 9)^5 * (x - 9)^10 * (x - 7)^15 * 
(x + 7)^30 * (x - 5)^36 * (x + 3)^60 * (x + 5)^60 * 
(x + 1)^75 * (x - 3)^100 * (x - 1)^120