Ask Your Question
2

tutte_polynomial (sage, matroid theory) gives the wrong result

asked 2022-01-11 20:06:59 +0100

dingchangxin gravatar image

updated 2022-01-12 10:34:45 +0100

slelievre gravatar image

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 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 flag offensive close merge delete

Comments

Welcome to Ask Sage! Thank you for your question.

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

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

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

1 Answer

Sort by ยป oldest newest most voted
2

answered 2022-01-12 11:17:49 +0100

rburing gravatar image

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
edit flag offensive delete link more

Comments

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

rburing gravatar imagerburing ( 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.

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2022-01-11 20:06:59 +0100

Seen: 166 times

Last updated: Jan 12 '22