#!/usr/bin/python """ Calculate a lower bound on the number of 5-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 576 with rank 161. The upper bound is 202 -- the rank of the join matrix. WARNING: This experiment takes a long time to complete. """ import _experiment 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()))