Ask Your Question

# Revision history [back]

### tutte_polynomial (sage, matroid theory) gives the wrong result

I have been using sage in my research recently. I am not sure which part is wrong but the following code gives the wrong results. The code is long, but I think you may only need to read the last four rows to understand my question. All the rows before that generate a matrix D where the columns are the cycles of the complete graph K_5 (each cycle is a vector in Z^10, 10 is the number of edges.) Then I produce a linear matroid from D and calculate T(2,0) using tutte_polynomial(). The weird thing is that the result is an odd number, which is impossible because the Tutte polynomial has no constant term. The more weird thing is that if I repeat the order again, I get a different result. If I run the code for the graph K_4, nothing is wrong, which is why I need to give the complete code. The code is run by CoCalc.

import numpy as np
from sage.matroids.advanced import *

graph=graphs.CompleteGraph(5)

g = graph.to_directed()
allcycles=g.all_simple_cycles()
nv=g.order() #nv is number of vertices
ne=nv*(nv-1)/2 #ne is the number of edges
ncycle=(len(allcycles)-g.size()/2)/2 #ncycle is number of simple cycles

def cycle(array): #array is a cycle in vertices notation eg. [0,1,2,3,0]
l=len(array)-1 #l is the length of the cycle
if l<=2:
return(False)
C=np.zeros(nv*(nv-1)/2) #C is to be a cycle in Z^E
for X in range(l):
i=array[X]+1
j=array[X+1]+1
if i<j:
C[(2*nv-i)*(i-1)/2+j-i-1]=1
else:
C[(2*nv-j)*(j-1)/2+i-j-1]=-1
return(C)

D=np.zeros((ne,ncycle*2)) #D is all directed cycles
X=0
for list in allcycles:
array=np.array(list)
if len(array)>3:
D[:,X]=cycle(array).transpose()
X=X+1

for X in range(ncycle): #reduce D so that D is all cycles with one orientation
positivecolumn=D[:, X]
Y=X+1
while (D[:, Y]+positivecolumn).any()!=0:
Y=Y+1
D=np.delete(D, Y, 1)

print(D)
M=Matroid(Matrix(D))
print("M.tutte_polynomial(2,0)=", M.tutte_polynomial(2,0))
print("M.tutte_polynomial(2,0)=", M.tutte_polynomial(2,0))


The results are

[[ 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0. 0. 0. 0. 0.] [-1. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 0. 1. 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 1. 1. 1. 1. 0. 0.] [ 0. -1. 0. -1. 0. 1. 0. 0. 0. 0. -1. 0. 0. 0. 0. -1. -1. 0. 0. -1. 1. 1. 0. 0. 0. 0. -1. 0. 0. -1. 0. 0. -1. 0. -1. 1. 1.] [ 0. 0. -1. 0. -1. -1. 0. 0. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1. -1. 0. -1. -1. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1. 0. -1. 0. -1. -1.] [ 1. 0. 0. 0. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 0. 0. -1. -1. 0. 0. 0. 0. 1. 1. 0. 1. 1. 0. 0. 0. 0. -1. -1. 0. 0. 1. -1.] [ 0. 1. 0. 0. 0. 0. -1. 0. 1. 0. 0. 0. 1. 1. 0. 0. 1. 0. 0. 0. -1. 0. 0. -1. 1. 0. 0. 1. 1. 0. 0. 1. 0. -1. 1. -1. 0.] [ 0. 0. 1. 0. 0. 0. 0. -1. -1. 0. 0. 0. 0. 0. 1. 1. 0. 1. 0. 0. 1. 0. -1. 0. -1. 0. 0. 0. 0. 1. 1. 0. 1. 1. -1. 0. 1.] [ 0. 0. 0. 1. 0. 0. 1. 0. 0. 1. 1. 0. -1. 0. 0. 0. 0. 0. 1. 0. 0. -1. 1. 0. -1. 1. 0. -1. 0. 1. -1. 0. 0. 1. 0. 0. -1.] [ 0. 0. 0. 0. 1. 0. 0. 1. 0. -1. 0. 1. 0. 0. -1. 0. 0. 0. 0. 1. 0. 1. 0. 1. 1. 0. 1. 1. -1. -1. 0. 0. 0. 0. 1. 1. 0.] [ 0. 0. 0. 0. 0. 1. 0. 0. 1. 1. 0. 0. 0. 1. 0. -1. 0. 0. 1. -1. 0. 0. 1. -1. 0. 1. -1. 0. 1. 0. -1. 1. -1. 0. 0. 0. 0.]] M.tutte_polynomial(2,0)= 46229 M.tutte_polynomial(2,0)= 52640

 2 None slelievre 17654 ●22 ●160 ●348 http://carva.org/samue...

### tutte_polynomial (sage, matroid theory) gives the wrong result

I have been using sage in my research recently. I am not sure which part is wrong but the following code gives the wrong results. The code is long, but I think you may only need to read the last four rows to understand my question. All the rows before that generate a matrix D where the columns are the cycles of the complete graph K_5 (each cycle is a vector in Z^10, 10 is the number of edges.) Then I produce a linear matroid from D and calculate T(2,0) using tutte_polynomial(). The weird thing is that the result is an odd number, which is impossible because the Tutte polynomial has no constant term. The more weird thing is that if I repeat the order again, I get a different result. If I run the code for the graph K_4, nothing is wrong, which is why I need to give the complete code. The code is run by CoCalc.

import numpy as np
from sage.matroids.advanced import *

graph=graphs.CompleteGraph(5)
graph = graphs.CompleteGraph(5)

g = graph.to_directed()
allcycles=g.all_simple_cycles()
nv=g.order() #nv allcycles = g.all_simple_cycles()
nv = g.order()  # nv is number of vertices
ne=nv*(nv-1)/2 #ne ne = nv*(nv-1)/2  # ne is the number of edges
ncycle=(len(allcycles)-g.size()/2)/2 #ncycle ncycle = (len(allcycles)-g.size()/2)/2  # ncycle is number of simple cycles

def cycle(array): #array  # array is a cycle in vertices notation eg. [0,1,2,3,0]
l=len(array)-1 #l l = len(array) - 1  # l is the length of the cycle
if l<=2:
return(False)
C=np.zeros(nv*(nv-1)/2) #C l <= 2:
return False
C = np.zeros(nv*(nv-1)/2)  # C is to be a cycle in Z^E
for X in range(l):
i=array[X]+1
j=array[X+1]+1
i = array[X] + 1
j = array[X+1] + 1
if i<j:
C[(2*nv-i)*(i-1)/2+j-i-1]=1
i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1]=-1
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)

D=np.zeros((ne,ncycle*2)) #D D = np.zeros((ne,ncycle*2))  # D is all directed cycles
X=0
X = 0
for list in allcycles:
array=np.array(list)
array = np.array(list)
if len(array)>3:
D[:,X]=cycle(array).transpose()
X=X+1
len(array) > 3:
D[:, X] = cycle(array).transpose()
X = X + 1

for X in range(ncycle): #reduce  # reduce D so that D is all cycles with one orientation
positivecolumn=D[:, positivecolumn = D[:, X]
Y=X+1
Y = X + 1
while (D[:, Y]+positivecolumn).any()!=0:
Y=Y+1
D=np.delete(D, any(D[:, Y] + positivecolumn):
Y = Y + 1
D = np.delete(D, Y, 1)

print(D)
M=Matroid(Matrix(D))
print("M.tutte_polynomial(2,0)=", M.tutte_polynomial(2,0))
print("M.tutte_polynomial(2,0)=", M.tutte_polynomial(2,0))
M = Matroid(Matrix(D))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))


The results are

[[ 1.  1.  1.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  1.  1.  1.  0.  0.
0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  1.  1.  1.  0.  0.  0.  0.  0.
0.]
[-1.  0.  0.  1.  1.  0.  0.  0.  0.  0.  0.  0. -1.  0. -1.  0.  1.  1.
1.  1.  0.  0.  0.  0.  0.  0.  0.  0. -1.  0. -1.  1.  1.  1.  1.  0.
0.]
[ 0. -1.  0. -1.  0.  1.  0.  0.  0.  0. -1.  0.  0.  0.  0. -1. -1.  0.
0. -1.  1.  1.  0.  0.  0.  0. -1.  0.  0. -1.  0.  0. -1.  0. -1.  1.
1.]
[ 0.  0. -1.  0. -1. -1.  0.  0.  0.  0.  0. -1.  0. -1.  0.  0.  0. -1.
-1.  0. -1. -1.  0.  0.  0. -1.  0. -1.  0.  0.  0. -1.  0. -1.  0. -1.
-1.]
[ 1.  0.  0.  0.  0.  0.  1.  1.  0.  0.  1.  1.  0.  0.  0.  0. -1. -1.
0.  0.  0.  0.  1.  1.  0.  1.  1.  0.  0.  0.  0. -1. -1.  0.  0.  1.
-1.]
[ 0.  1.  0.  0.  0.  0. -1.  0.  1.  0.  0.  0.  1.  1.  0.  0.  1.  0.
0.  0. -1.  0.  0. -1.  1.  0.  0.  1.  1.  0.  0.  1.  0. -1.  1. -1.
0.]
[ 0.  0.  1.  0.  0.  0.  0. -1. -1.  0.  0.  0.  0.  0.  1.  1.  0.  1.
0.  0.  1.  0. -1.  0. -1.  0.  0.  0.  0.  1.  1.  0.  1.  1. -1.  0.
1.]
[ 0.  0.  0.  1.  0.  0.  1.  0.  0.  1.  1.  0. -1.  0.  0.  0.  0.  0.
1.  0.  0. -1.  1.  0. -1.  1.  0. -1.  0.  1. -1.  0.  0.  1.  0.  0.
-1.]
[ 0.  0.  0.  0.  1.  0.  0.  1.  0. -1.  0.  1.  0.  0. -1.  0.  0.  0.
0.  1.  0.  1.  0.  1.  1.  0.  1.  1. -1. -1.  0.  0.  0.  0.  1.  1.
0.]
[ 0.  0.  0.  0.  0.  1.  0.  0.  1.  1.  0.  0.  0.  1.  0. -1.  0.  0.
1. -1.  0.  0.  1. -1.  0.  1. -1.  0.  1.  0. -1.  1. -1.  0.  0.  0.
0.]]
M.tutte_polynomial(2,0)= M.tutte_polynomial(2, 0) = 46229
M.tutte_polynomial(2,0)= 52640 
M.tutte_polynomial(2, 0) = 52640 
 3 None slelievre 17654 ●22 ●160 ●348 http://carva.org/samue...

### tutte_polynomial (sage, matroid theory) gives the wrong result

I have been using sage Sage in my research recently. recently.

I am not sure which part is wrong but the following code code gives the wrong results. The code is long, but I think you may may only need to read the last four rows to understand my question. question.

All the rows before that generate a matrix D D where the columns are the cycles of the complete graph K_5 K_5 (each cycle is a vector in Z^10, Z^10, 10 is the number of edges.) edges.)

Then I produce a linear matroid from D D and calculate T(2,0) T(2, 0) using tutte_polynomial(). tutte_polynomial(). The weird thing is that the result result is an odd number, which is impossible because the Tutte polynomial polynomial has no constant term. The more weird thing is that if I repeat the the order again, I get a different result. result.

If I run the code for the graph K_4, K_4, nothing is wrong, wrong, which is why I need to give the complete code. code. The code is run by CoCalc.

import numpy as np
from sage.matroids.advanced import *

graph = graphs.CompleteGraph(5)

g = graph.to_directed()
allcycles = g.all_simple_cycles()
nv = g.order()  # nv is number of vertices
ne = nv*(nv-1)/2  # ne is the number of edges
ncycle = (len(allcycles)-g.size()/2)/2  # ncycle is number of simple cycles

def cycle(array):  # array is a cycle in vertices notation eg. [0,1,2,3,0]
l = len(array) - 1  # l is the length of the cycle
if l <= 2:
return False
C = np.zeros(nv*(nv-1)/2)  # C is to be a cycle in Z^E
for X in range(l):
i = array[X] + 1
j = array[X+1] + 1
if i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)

D = np.zeros((ne,ncycle*2))  # D is all directed cycles
X = 0
for list in allcycles:
array = np.array(list)
if len(array) > 3:
D[:, X] = cycle(array).transpose()
X = X + 1

for X in range(ncycle):  # reduce D so that D is all cycles with one orientation
positivecolumn = D[:, X]
Y = X + 1
while any(D[:, Y] + positivecolumn):
Y = Y + 1
D = np.delete(D, Y, 1)

print(D)
M = Matroid(Matrix(D))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))


The results are

[[ 1.  1.  1.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  1.  1.  1.  0.  0.
0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  1.  1.  1.  0.  0.  0.  0.  0.  0.]
[-1.  0.  0.  1.  1.  0.  0.  0.  0.  0.  0.  0. -1.  0. -1.  0.  1.  1.
1.  1.  0.  0.  0.  0.  0.  0.  0.  0. -1.  0. -1.  1.  1.  1.  1.  0.  0.]
[ 0. -1.  0. -1.  0.  1.  0.  0.  0.  0. -1.  0.  0.  0.  0. -1. -1.  0.
0. -1.  1.  1.  0.  0.  0.  0. -1.  0.  0. -1.  0.  0. -1.  0. -1.  1.  1.]
[ 0.  0. -1.  0. -1. -1.  0.  0.  0.  0.  0. -1.  0. -1.  0.  0.  0. -1.
-1.  0. -1. -1.  0.  0.  0. -1.  0. -1.  0.  0.  0. -1.  0. -1.  0. -1. -1.]
[ 1.  0.  0.  0.  0.  0.  1.  1.  0.  0.  1.  1.  0.  0.  0.  0. -1. -1.
0.  0.  0.  0.  1.  1.  0.  1.  1.  0.  0.  0.  0. -1. -1.  0.  0.  1. -1.]
[ 0.  1.  0.  0.  0.  0. -1.  0.  1.  0.  0.  0.  1.  1.  0.  0.  1.  0.
0.  0. -1.  0.  0. -1.  1.  0.  0.  1.  1.  0.  0.  1.  0. -1.  1. -1.  0.]
[-1.  0.  0.  1.  1.  0.  0.  0.  0.  0.  0.  0. -1.  0. -1.  0.  1. [ 0.  0.  1.  0.  0.  0.  0. -1. -1.  0.  0.  0.  0.  0.  1.  1.  0.  1.
1.  1.  0.  0.  0.  0.  0.  0.  0.  0. -1.  0. -1.  1.  1.  1.  1. 0.  0.  1.  0. -1.  0. -1.  0.  0.  0.  0.  1.  1.  0.  1.  1. -1.  0.  1.]
[ 0.  0.  0.  1.  0.  0.  1.  0.  0.  1.  1.  0. -1.  0.  0.  0.  0.  0.
1.  0.  0. -1.  1.  0. -1.  1.  0. -1.  0.  1. -1.  0.  0.  1.  0.  0. -1.]
[ 0.  0.  0.  0.  1.  0.  0.  1.  0. -1.  0.  1.  0.  0. -1.  0.  0.  0.
0.  1.  0.  1.  0.  1.  1.  0.  1.  1. -1. -1.  0.  0.  0.  0.  1.  1.  0.]
[ 0. -1.  0. -1.  0.  1.  0.  0.  0.  0. -1.  0.  0.  0.  0. -1. -1.  0.  0.  0.  0.  1.  0.  0.  1.  1.  0.  0.  0.  1.  0. -1.  0.  0.
0. -1.  1.  1.  0.  0.  0.  0. -1.  0.  0. -1.  0.  0. -1.  0. -1.  1.
1.]
[ 0.  0. -1.  0. -1. -1.  0.  0.  0.  0.  0. -1.  0. -1.  0.  0.  0. -1.
-1.  0. -1. -1.  0.  0.  0. -1.  0. -1.  0.  0.  0. -1.  0. -1.  0. -1.
-1.]
[ 1.  0.  0.  0.  0.  0.  1.  1.  0.  0.  1.  1.  0.  0.  0.  0. -1. -1.
0.  0.  0.  0.  1.  1.  0.  1.  1.  0.  0.  0.  0. -1. -1.  0.  0.  1.
-1.]
[ 0.  1.  0.  0.  0.  0. -1.  0.  1.  0.  0.  0.  1.  1.  0.  0.  1.  0.
0.  0. -1.  0.  0. -1.  1.  0.  0.  1.  1.  0.  0.  1.  0. -1.  1. -1.
0.]
[ 0.  0.  1.  0.  0.  0.  0. -1. -1.  0.  0.  0.  0.  0.  1.  1.  0.  1.
0.  0.  1.  0. -1.  0. -1.  0.  0.  0.  0.  1.  1.  0.  1.  1. -1.  0.
1.]
[ 0.  0.  0.  1.  0.  0.  1.  0.  0.  1.  1.  0. -1.  0.  0.  0.  0.  0.
1.  0.  0. -1.  1.  0. -1.  1.  0. -1.  0.  1. -1.  0.  0.  1.  0.  0.
-1.]
[ 0.  0.  0.  0.  1.  0.  0.  1.  0. -1.  0.  1.  0.  0. -1.  0.  0.  0.
0.  1.  0.  1.  0.  1.  1.  0.  1.  1. -1. -1.  0.  0.  0.  0.  1.  1.
0.]
[ 0.  0.  0.  0.  0.  1.  0.  0.  1.  1.  0.  0.  0.  1.  0. -1.  0.  0.
1. -1.  0.  0.  1. -1.  0.  1. -1.  0.  1.  0. -1.  1. -1.  0.  0.  0.
1. -1.  0.  0.  1. -1.  0.  1. -1.  0.  1.  0. -1.  1. -1.  0.  0.  0.  0.]]
M.tutte_polynomial(2, 0) = 46229
M.tutte_polynomial(2, 0) = 52640