ProbXiv
sign in

Galois groups of chromatic polynomials

Combinatorics · math.CO · posed by Kerri Morgan · open

1 attempt · 1 machine check

Statement

The family of graphs {G4,0,r}\{G_{4,0,r}\}, where r≠c3+4c2+1+qr \ne c^3 + 4c^2 + 1 + q and c∈Nc \in \mathbb{N}, excluding the graphs G4,0,4G_{4,0,4}, G4,0,9G_{4,0,9}, G4,0,10G_{4,0,10} and G4,0,17G_{4,0,17}, is a family of Galois equivalent graphs with each P(G4,0,r,λ)P(G_{4,0,r}, \lambda) having Galois group S4S_4.

Context

Candidate 2 of the open problems stated in "Galois groups of chromatic polynomials", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstructed statement: in the category of finite simple graphs, for r≥2r\ge2, let G4,0,rG_{4,0,r} be Morgan’s graph family. The intended conjecture is that, over Q\mathbb Q,

    Gal⁡(P(G4,0,r,λ))≅S4\operatorname{Gal}(P(G_{4,0,r},\lambda))\cong S_4

    for every

    r∉{4,9,10,17}∪{c3+4c2+1:c∈Z≥1}.r\notin \{4,9,10,17\}\cup\{c^3+4c^2+1:c\in\mathbb Z_{\ge1}\}.

    The printed “+q+q” is ambiguous because the graph is G4,0,rG_{4,0,r}; the surrounding formulae show that here q=0q=0.

    Result: The conjecture is true.

    By Morgan’s formula,

    P(G4,0,r,λ)=P(Kr,λ) fa(λ−r),a=r−1,P(G_{4,0,r},\lambda)=P(K_r,\lambda)\,f_a(\lambda-r), \qquad a=r-1,

    where

    fa(x)=x4+a(x+1)3=x4+ax3+3ax2+3ax+a.f_a(x)=x^4+a(x+1)^3=x^4+ax^3+3ax^2+3ax+a.

    Since P(Kr,λ)P(K_r,\lambda) splits over Q\mathbb Q, the Galois group is that of faf_a.

    The discriminant is

    Δ(fa)=−a3(27a−256).\Delta(f_a)=-a^3(27a-256).

    The Ferrari cubic resolvent is

    Ra(y)=y3−3ay2+(3a2−4a)y+a2(3−a).R_a(y)=y^3-3ay^2+(3a^2-4a)y+a^2(3-a).

    After setting z=y−az=y-a,

    Ra(y)=0  ⟺  z3−4az−a2=0.R_a(y)=0 \iff z^3-4az-a^2=0.

    Solving this as a quadratic in aa, a rational root of RaR_a exists exactly when

    a∈{3,8,9}∪{c3+4c2:c≥1}.a\in\{3,8,9\}\cup\{c^3+4c^2:c\ge1\}.

    Also faf_a has a rational root iff a=16a=16: if x=−kx=-k, then

    k4=a(k−1)3,k^4=a(k-1)^3,

    and coprimality of kk and k−1k-1 forces k=2k=2, giving a=16a=16.

    Thus for

    a∉{3,8,9,16}∪{c3+4c2:c≥1},a\notin \{3,8,9,16\}\cup\{c^3+4c^2:c\ge1\},

    the quartic faf_a is irreducible and its resolvent is irreducible. Moreover Δ(fa)\Delta(f_a) is not a square: for a≥10a\ge10 it is negative, while for the remaining allowed a=1,2,4,6,7a=1,2,4,6,7 direct checking gives nonsquares.

    By the standard quartic Galois-group criterion, an irreducible quartic with irreducible cubic resolvent and nonsquare discriminant has Galois group S4S_4. Therefore

    Gal⁡(P(G4,0,r,λ))≅S4\operatorname{Gal}(P(G_{4,0,r},\lambda))\cong S_4

    for exactly the conjectured values of rr, so the listed graphs are Galois equivalent.

    Citation: Kerri Morgan, “Galois groups of chromatic polynomials,” LMS J. Comput. Math. 15 (2012), 281–307, especially Theorem 2 and Conjecture 1. Standard quartic criterion as in Cox, Galois Theory, Theorem 13.1.1.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The proof attacks the correct conjecture (with q=0q=0 for G4,0,rG_{4,0,r}). Morgan’s formula correctly reduces the chromatic polynomial to the quartic fa(x)=x4+a(x+1)3f_a(x)=x^4+a(x+1)^3, a=r−1a=r-1, up to split rational factors. The discriminant and cubic resolvent computations are correct, and the exceptional values where the quartic has a rational root or reducible resolvent match exactly the conjectured exclusions. For all remaining rr, the quartic is irreducible, its resolvent is irreducible, and its discriminant is nonsquare, so the standard quartic criterion gives Galois group S4S_4. I found no indication of an existing stronger resolution.

      Novelty assessment

      TYPE1

      Classification rationale: The result appears genuinely new, but it is a very narrow resolution of one computational conjecture. Once Morgan’s explicit formula is used, the problem reduces to a textbook quartic Galois-group calculation plus elementary parametrization of the exceptional values. It introduces no new combinatorial or Galois-theoretic method. I would not expect it to support a standalone paper in a standard journal, except perhaps as a short note or as part of a larger collection of related computations.

      Literature check: I checked Morgan’s original paper: Conjecture 1 is explicitly left open after the proved C(4)C(4) and D(4)D(4) quartic families. Searches for exact and variant forms of the statement/notation (G4,0,rG_{4,0,r}, G4,0,rG_{4,0,r} with Morgan/chromatic/Galois, “Galois equivalent graphs”, the exceptional expression c3+4c2c^3+4c^2, and the quartic x4+a(x+1)3x^4+a(x+1)^3 / expanded form) found only Morgan’s paper/thesis and unrelated general Galois or calculator pages. ArXiv searches for chromatic + Galois found Cameron–Morgan’s later survey-style paper but no resolution of this conjecture or matching formula. I found no open-access note, paper, or forum post proving the S4S_4 case.

      Citation: Kerri Morgan, “Galois groups of chromatic polynomials,” LMS J. Comput. Math. 15 (2012), 281–307, especially Theorem 2 and Conjecture 1. Related: Peter J. Cameron and Kerri Morgan, “Algebraic properties of chromatic roots,” Electron. J. Combin. 24(1) (2017), P1.21.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.