Skip to content
Snippets Groups Projects
Select Git revision
  • 31f171adf74a9633cb7888971787430164fc353a
  • master default protected
2 results

cdc_5_boundaries.py

Blame
  • cdc_5_boundaries.py 1.45 KiB
    #!/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()))