cdc_5_boundaries.py

#!/usr/bin/python

"""
Calculate a lower bound on the number of 4-boundaries
of a linear representation of the number of circuit double
covers.

It uses cyclic ladder gadgets with sizes 2 up to 7 with
permutations of all half-edges except the first one.
This gives matrix of size 36 with rank 21.
"""

import sys, os
sys.path.append(os.path.dirname(__file__) + "/..")

from itertools import permutations
from graph_tools.all import *


def LadderGadget(k):
  g = CyclicLadder().gadget(k)
  return Gadget.join([g, CUBIC_VERTEX], [((1, 1), (2, 1))],
    [(2,2), (2,3), (1,2), (1,3), (1,4)])

ladders = list(map(LadderGadget, range(2, 8)))
gadgets = [ l.permute((1,) + p) 
  for l in ladders for p in permutations([2, 3, 4, 5])  ] + [
  l.permute((3,) + p) for l in ladders for p in permutations([1, 2, 4, 5])  ] + [
  l.permute((4,) + p) for l in ladders for p in permutations([1, 2, 3, 5])  ] + [
  l.permute((5,) + p) for l in ladders for p in permutations([1, 2, 3, 4])  ]

M = parameter_matrix(CircuitDoubleCover, gadgets, threads=None)
pivot_rows = M.pivot_rows()

J = edge_model_join_matrix(CircuitDoubleCover, 5, threads=None)

if __name__ == "__main__":
  print("Circuit double covers -- 5-boundaries:")
  print("Matrix of size %i with rank %i" % (M.nrows(), M.rank()))
  print("  Pivot rows: %s" % (pivot_rows,))
  print("Upper bound: Join matrix of size %i with rank %i" % (J.nrows(), J.rank()))