#7052: [with patch, needs review] Chromatic polynomial calculated incorrectly
--------------------------+-------------------------------------------------
Reporter: AJonsson | Owner: rlm
Type: defect | Status: new
Priority: minor | Milestone: sage-4.1.3
Component: graph theory | Keywords:
Reviewer: | Author:
Merged: |
--------------------------+-------------------------------------------------
Comment(by 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/
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7052#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
