# 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

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.]
[ 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

edit retag close merge delete

( 2022-01-12 10:24:42 +0100 )edit

Thank you for editing my question so that it looks neat. This is a wonderful place.

( 2022-01-13 04:28:11 +0100 )edit

Sort by » oldest newest most voted

Don't use floating point numbers, vectors or matrices (here: numpy arrays) if you want to do an exact computation.

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 None
C = zero_vector(ZZ, ne)  # 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 = matrix(ZZ, ne, ncycle*2)  # D is all directed cycles
X = 0
for array in allcycles:
if len(array) > 3:
D.set_column(X, cycle(array))
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 = D.delete_columns([Y])

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


Output:

[ 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) = 89280
M.tutte_polynomial(2, 0) = 89280

more

Maybe the Matroid constructor should give a warning or an error when a matrix with floating point entries is passed.

( 2022-01-12 11:25:09 +0100 )edit
1

Thank you so much for your answer! You have even corrected the code, which saves me a lot of time.

( 2022-01-13 04:21:56 +0100 )edit