Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download

Independent set Nullstellesnatz certificate example

Project: Test
Views: 68
def Li_next(Li, i, alpha, r): return (i*Li/(alpha + r - i)) #end def g = graphs.CycleGraph(5) g.plot().show() # create the independent set ideal for this graph # looking for an idependent set if size k > alpha(G) # assume a k = 6 P = PolynomialRing(QQ, g.order(), 'x', order="lex") # over F2 x = P.gens() vp = 0 for i in range(0, g.order()): vp = vp + x[i] #end for # subtract off k vp = vp - k; alpha = 2; r = k - alpha; L0 = 1 / (alpha + r) L1 = Li_next(L0, 1, alpha, r) L2 = Li_next(L1, 2, alpha, r) print "L0 = " + str(L0) + ", L1 = " + str(L1) + ", L2 = " + str(L2) A = L2*(x[0]*x[2]+x[0]*x[3]+x[1]*x[3]+x[1]*x[4]+x[2]*x[4]) + L1*(x[0]+x[1]+x[2]+x[3]+x[4]) + L0 #A = L2*(x[0]*x[2]+x[0]*x[3]+x[1]*x[3]+x[1]*x[4]+x[2]*x[4]) Q0 = L1 + L2*(x[2]+x[3]); # 0*2, 0*3 are independent sets Q1 = L1 + L2*(x[3]+x[4]); # 1*3, 1*4 are independent sets Q2 = L1 + L2*(x[0]+x[4]); # 2*0, 2*4 are independent sets Q3 = L1 + L2*(x[0]+x[1]); # 3*0, 3*1 are independent sets Q4 = L1 + L2*(x[1]+x[2]); # 4*1, 4*2 are independent sets # 01: 0*1, 1*0 ## 02*1 03*1, 13*0 14*0 ### 012 014 # 04: 0*4, 4*0 ## 02*4 03*4, 14*0, 24*0 ## 014 034 # 12: 1*2, 2*1 ## 13*2 14*2, 02*1 24*1 ### 012 123 (note 012 has already been handled by 02*1) # 23: 2*3, 3*2 ## 02*3 24*3, 13*2 03*2 ### 123 234 # 34: 3*4, 4*3 ## 03*4 13*4, 14*3 24*3 ### 234 034 Q01 = L2*(x[2] + x[3]) + L1; # 0 \in I, 0*1 (01), 02*1 (012), 03*1 (013), min edge 01 Q01 = Q01 + L2*(x[3] + x[4]) + L1; # 1 \in I, 1*0 (01), 13*0 (013), 14*0 (014), min edge 01 Q04 = L2*(x[2] + x[3]) + L1; # 0 \in I, 0*4 (04), 02*4 (024), 03*4 (034) Q04 = Q04 + L2*(x[2]) + L1; # 4 \in I, 4*0 (04), 14*0 (014, min edge = 01, handled already), 24*0 (024) Q12 = L2*(x[3]+x[4])+L1; # 1 \in I, 1*2 (12), 13*2 (123), 14*2 (124), min edge 12 Q12 = Q12 + L2*(x[4])+ L1; # 2 \in I, 2*1 (12), 24*1 (124), 02*4 (024) Q23 = L2*(x[0]+x[4]) + L1; # 2 \in I, 2*3 (23), 24*3 (234), 02*3 (023) Q23 = Q23 + L2*(x[0]) + L1; # 3 in I, 3*2 (23), 13*2 (123), 03*2 (023) Q34 = L2*(x[1]) + L1; # 3 in I, 3*4 (34), 03*4 (034) 13 Q34 = Q34 + L2*(x[1]) + L1; # 4 in I, 4*3 (34) print "Observe one monomial for every independent set in G!!" -A print "Observe the certificate simplifies to 1!!" cert = -A*vp + Q0*(x[0]^2-x[0]) + Q1*(x[1]^2-x[1]) + Q2*(x[2]^2-x[2]) + Q3*(x[3]^2-x[3]) + Q4*(x[4]^2-x[4]) cert = cert + Q01*x[0]*x[1] + Q04*x[0]*x[4] + Q12*x[1]*x[2]+Q23*x[2]*x[3]+Q34*x[3]*x[4] cert
L0 = 1/6, L1 = 1/30, L2 = 1/60 Observe one monomial for every independent set in G!! -1/60*x0*x2 - 1/60*x0*x3 - 1/30*x0 - 1/60*x1*x3 - 1/60*x1*x4 - 1/30*x1 - 1/60*x2*x4 - 1/30*x2 - 1/30*x3 - 1/30*x4 - 1/6 Observe the certificate simplifies to 1!! 1