# Ticket #7052(closed defect: fixed)

Opened 4 years ago

## Chromatic polynomial calculated incorrectly

Reported by: Owned by: AJonsson rlm major sage-4.2.1 graph theory jason Mike Hansen Anders Jonsson, Robert Miller sage-4.2.1.alpha0

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)
```

## Change History

### comment:1 Changed 4 years ago by AJonsson

• Description modified (diff)

### Changed 4 years ago by AJonsson

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

### comment:3 Changed 4 years ago by AJonsson

• Summary changed from Chromatic polynomial calculated incorrectly to [with patch, needs review] Chromatic polynomial calculated incorrectly

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 x11 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).

### Changed 4 years ago by AJonsson

Smaller, nicer patch

### comment:4 Changed 4 years ago by AJonsson

• Priority changed from minor to major

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.

### comment:5 Changed 4 years ago by 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.

### comment:6 Changed 4 years ago by AJonsson

• Status changed from needs_review to needs_work
• Summary changed from [with patch, needs review] Chromatic polynomial calculated incorrectly to Chromatic polynomial calculated incorrectly

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.

### comment:7 Changed 4 years ago by 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.

### comment:8 Changed 4 years ago by 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.

### comment:9 Changed 4 years ago by 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.

### comment:10 Changed 4 years ago by 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.

### Changed 4 years ago by rlm

Uses mpz_t instead of long long

### comment:11 Changed 4 years ago by rlm

• Status changed from needs_work to needs_review

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.

### comment:12 Changed 4 years ago by 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.

### comment:13 Changed 4 years ago by timmcmillen

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

### comment:14 Changed 4 years ago by mhansen

• Status changed from needs_review to positive_review
• Reviewers set to Mike Hansen
• Authors set to Anders Jonsson, Robert Miller

### comment:15 Changed 4 years ago by mhansen

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-4.2.1.alpha0
Note: See TracTickets for help on using tickets.