Chromatic polynomial calculated incorrectly

[AJonsson]

Playing around with some graphs I noticed that even though the graph below (the McGee? graph) not is bipartite, it is claimed to have chromatic number 2 (This should be 3).

The error seems to be in the calculation of the chromatic polynomial, as there is no chromatic root (x-2) in the factorization of the chromatic polynomial, which is then used to say that there exists 2-colorings of the graph.

Code to reproduce:

G = Graph({0:[1,12,23], 1:[0,2,8], 2:[1,3,19], 3:[2,4,15], 4:[3,5,11],\
            5:[4,6,22], 6:[5,7,18], 7:[6,8,14], 8:[1,7,9], 9:[8,10,21], 10:[9,11,17],\
            11:[4,10,12], 12:[0,11,13], 13:[12,14,20], 14:[7,13,15],\
            15:[3,14,16], 16:[15,17,23], 17:[10,16,18], 18:[6,17,19], 19:[2,18,20], 20:[13,19,21],\
            21:[9,20,22], 22:[5,21,23], 23:[0,16,22]})
print G.is_bipartite()
print G.chromatic_number()
print G.chromatic_polynomial().factor()

Output from code above:

False
2
(x - 1) * x * (x^22 - 35*x^21 + 595*x^20 - 6545*x^19 + 52360*x^18 -
324632*x^17 + 1623128*x^16 - 6723558*x^15 + 23521860*x^14 -
70477280*x^13 + 182703380*x^12 - 412698250*x^11 + 815778984*x^10 +
2881630536*x^9 + 2143156981*x^8 + 1464159543*x^7 + 3227470630*x^6 +
1165679734*x^5 + 2520767421*x^4 + 2668980011*x^3 + 789733264*x^2 -
257225680*x + 42167160)

[AJonsson]

Allow for larger coeffecients in chromatic polynomial. Add McGee? graph generator.

[AJonsson]

Figured out the cause of the miscalculations. Coefficients of the chromatic polynomial are saved as 32-bit integers in Sage, so numbers larger than 2,147,483,647 will come out wrong.

Comparison of the computed chromatic polynomial for the McGee? graph using Sage and using a program made by Pearce and Haggard[1]:

Chromatic polynomial using Pearce:

x^24 - 36*x^23 + 630*x^22 - 7140*x^21 + 58905*x^20 - 376992*x^19 +
1947760*x^18 - 8346686*x^17 + 30245418*x^16 - 93999140*x^15 +
253180660*x^14 - 595401630*x^13 + 1228477234*x^12 - 2229115744*x^11 +
3556493741*x^10 - 4973964734*x^9 + 6058278383*x^8 - 6356758192*x^7 +
5650054983*x^6 - 4146754706*x^5 + 2415720549*x^4 - 1046958944*x^3 +
299392840*x^2 - 42167160*x

Using Sage:

x^24 - 36*x^23 + 630*x^22 - 7140*x^21 + 58905*x^20 - 376992*x^19 +
1947760*x^18 - 8346686*x^17 + 30245418*x^16 - 93999140*x^15 +
253180660*x^14 - 595401630*x^13 + 1228477234*x^12 + 2065851552*x^11 -
738473555*x^10 - 678997438*x^9 + 1763311087*x^8 - 2061790896*x^7 +
1355087687*x^6 + 148212590*x^5 - 1879246747*x^4 - 1046958944*x^3 +
299392840*x^2 - 42167160*x

If we now look at the coefficients for x^{11 we see that the difference between them is}

2065851552 - (-2229115744) = 4294967296 = 2^32

i.e 32-bit integer.

solution: replace int with long long in suitable places in /sage/graphs/chrompoly.pyx so that 64 bits are used to describe each coefficient value (long won't suffice, as it is only 32-bit)

Attaching a patch that changes relevant variables to long long, as well as adding the McGee? graph to named graphs as a doctest to show that the changes give a correct answer (the chromatic number should be 3).

[1]:  http://homepages.mcs.vuw.ac.nz/~djp/tutte/

[AJonsson]

Smaller, nicer patch

[AJonsson]

Found the wonderful graphs.LCFGraph() function, so it became clear to me that a constructor for the McGee? graph was redundant, when a simple graphs.LCFGraph(24, [12,7,-7], 8) worked just as fine.

New version of the patch just changes int to long long at the necessary places, and adds a test of the value of the chromatic polynomial at x=2, to see that it is 0 now.

Changing priority to major, as this clearly will happen to any graph that is sufficiently large.

[rlm]

Changing int to long long isn't really fixing the issue, it's just putting it off until someone uses a much larger graph. Why not use gmp integers instead? This seems like the natural solution to this problem.

[AJonsson]

Made some tries with gmp integers yesterday, but was unable to make it work. Will probably look further into it at a later date, but would certainly not grieve if anyone beats me to it and fixes the ticket before that.

[timmcmillen]

Indeed I had mean to report this bug, but I'm glad someone did. Instead of trying to patch the current code, why not just integrate the tuttee polynomial code from Pearce and Haggard linked above? Not only is their code about 100 times faster than the code currently in Sage (for the graphs I've been working with) but it has the added advantage of being able to efficiently compute both the tutte polynomial and the chromatic polynomial. The tutte polynomial of course has a variety of different applications. The authors had expressed an interest in getting the code integrated into Sage, but they weren't sure how to do it, and may not have the time themselves. The code is under a very permissive license, so integrating it should be feasible from that aspect.

[jason]

At first glance, the package looks nice. However, it relies on nauty, which doesn't have a license that allows incorporation in the standard Sage distribution. We could make the tutte polynomial package an optional spkg, though, and have the Sage functions use the package if it is installed. Or we could replace the functionality needing nauty with calls the equivalent code in the sage library.

[timmcmillen]

Hm, yes, I hadn't thought about the license on nauty. Part of the reason that the tutte code runs so fast is that nauty is rather optimized. Perhaps we could combine the methods you propose and replace the functionality needing nauty with sage code, but use nauty if it is installed as an optional spkg. That could provide a bridge until the Sage library code could be equally optimized or a better optimization could be found. If I recall, the only thing the tutte code calls nauty for is checking isomorphism, but it does it an awful lot. Unfortunately I don't have the coding skills to contribute, but I can help with testing or documentation.

[jason]

At any rate, if the patch above fixes the issue (can you test that?), then this patch maybe ought to go in and another ticket opened for integrating the package you mention into Sage.

[rlm]

Uses mpz_t instead of long long

[rlm]

This new patch should fix the original problem in a more rigorous manner.

As far as the Tutte polynomial, this is definitely a topic for another ticket.

[timmcmillen]

As soon as I figure out how to reverse the trac_7052_minimal.patch, I'll test yours. hg_sage.rollback() seemed logical, but didn't actually reverse the changes to the file. I'm trying to learn mercurial as we speak.

In case anyone is curious, trac_7052_minimal.patch still led to some issues where the resulting polynomial was off by a 32 bit integer.

[timmcmillen]

Ok, everything I've tested so far with the gmp patch checks out. I'll keep testing, but it looks good so far.