ProbXiv
sign in

A Polynomial Method for Counting Colorings of S-labeled Graphs

Number theory · math.CO · math.NT · posed by Samantha L. Dahlberg, Hemanshu Kaul, Jeffrey A. Mudrock · open

1 attempt · 1 machine check

Statement

If k is a power of a prime,

PLk(G,k)=PDP(G,k).P_{\mathcal{L}_{k}}(G,k)=P_{DP}(G,k).

Context

Candidate 1 of the open problems stated in "A Polynomial Method for Counting Colorings of S-labeled Graphs", 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: for every finite loopless graph GG and every prime power kk, if Lk\mathcal L_k denotes the affine-linear permutation group of Fk\mathbb F_k,

    Lk={x↦ax+b: a∈Fk\*, b∈Fk},\mathcal L_k=\{x\mapsto ax+b:\ a\in\mathbb F_k^\*,\ b\in\mathbb F_k\},

    then

    PLk(G,k)=PDP(G,k).P_{\mathcal L_k}(G,k)=P_{DP}(G,k).

    This is exactly Conjecture 5 in the cited paper: PS(G,k)P_S(G,k) is the minimum number of proper SS-labeling colorings over all SS-labelings of GG, and PDP=PSym⁡(Fk)P_{DP}=P_{\operatorname{Sym}(\mathbb F_k)}.

    Result: The conjecture is false already for k=4k=4.

    Let G=K3,3−eG=K_{3,3}-e, with bipartition

    X={x1,x2,x3},Y={y1,y2,y3},X=\{x_1,x_2,x_3\},\qquad Y=\{y_1,y_2,y_3\},

    and all edges except x1y2x_1y_2. Thus

    E(G)={x1y1,x1y3,x2y1,x2y2,x2y3,x3y1,x3y2,x3y3}.E(G)=\{x_1y_1,x_1y_3,x_2y_1,x_2y_2,x_2y_3,x_3y_1,x_3y_2,x_3y_3\}.

    Use the spanning tree

    T={x1y1,x1y3,x2y3,x3y3,x3y2}.T=\{x_1y_1,x_1y_3,x_2y_3,x_3y_3,x_3y_2\}.

    By switching, every L4\mathcal L_4-labeling is equivalent, with the same number of colorings, to one with identity labels on TT and affine labels p,q,r∈L4p,q,r\in\mathcal L_4 on x2y1,x3y1,x2y2x_2y_1,x_3y_1,x_2y_2.

    For fixed colors a,c,e∈F4a,c,e\in\mathbb F_4 on x1,x2,x3x_1,x_2,x_3, the numbers of choices for y3,y1,y2y_3,y_1,y_2 are respectively

    4−∣{a,c,e}∣,4−∣{a,p(c),q(e)}∣,4−∣{e,r(c)}∣.4-|\{a,c,e\}|,\qquad 4-|\{a,p(c),q(e)\}|,\qquad 4-|\{e,r(c)\}|.

    Hence the number of colorings is

    N(p,q,r)=∑a,c,e∈F4(4−∣{a,c,e}∣)(4−∣{a,p(c),q(e)}∣)(4−∣{e,r(c)}∣).N(p,q,r)=\sum_{a,c,e\in\mathbb F_4} (4-|\{a,c,e\}|)(4-|\{a,p(c),q(e)\}|)(4-|\{e,r(c)\}|).

    A finite check over the affine group L4={x↦ax+b}\mathcal L_4=\{x\mapsto ax+b\}, ∣L4∣=12|\mathcal L_4|=12, gives

    N(p,q,r)≥388N(p,q,r)\ge 388

    for all affine p,q,rp,q,r. Thus

    PL4(G,4)≥388.P_{\mathcal L_4}(G,4)\ge 388.

    The bound is attained, for example, by nonzero distinct translations p(x)=x+αp(x)=x+\alpha, q(x)=x+βq(x)=x+\beta, together with a suitable translation rr, so

    PL4(G,4)=388.P_{\mathcal L_4}(G,4)=388.

    Now label the three non-tree edges by the 4-cycles

    p=(0 1 ω ω+1),q=p−1,r=p−1,p=(0\,1\,\omega\,\omega+1),\qquad q=p^{-1},\qquad r=p^{-1},

    and label every tree edge by the identity. These are valid DP labels but are not affine over F4\mathbb F_4. Direct substitution in the above formula gives

    N(p,q,r)=384.N(p,q,r)=384.

    Therefore

    PDP(G,4)≤384<388=PL4(G,4).P_{DP}(G,4)\le 384<388=P_{\mathcal L_4}(G,4).

    So

    PL4(G,4)≠PDP(G,4).P_{\mathcal L_4}(G,4)\ne P_{DP}(G,4).

    Thus Conjecture 5 is disproved.

    Citation: Counterexample given here; no prior published disproof is being invoked.

    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 counterexample targets exactly Conjecture 5. The switching reduction and counting formula are valid for G=K3,3−eG=K_{3,3}-e. The key affine minimum is correct: for affine p,q∈L4=A4p,q\in \mathcal L_4=A_4, the count is minimized at 388388, attained by distinct nonzero translations and a suitable translation rr. The proposed non-affine DP labeling using a 4-cycle gives N=384N=384. Hence

      PDP(G,4)≤384<388=PL4(G,4),P_{DP}(G,4)\le 384<388=P_{\mathcal L_4}(G,4),

      so the conjecture is false. I found no prior published disproof in the available literature checks.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample appears genuinely new, but it is a very small finite/computational disproof of a recent “provocative” conjecture rather than a broad structural advance. It would be useful to the authors and perhaps as an erratum/short note, but by itself likely does not support a standalone standard-journal combinatorics paper.

      Literature check: I found no prior publication, preprint update, comment, or code/source record containing this counterexample or a stronger disproof. The current arXiv v2 still states Conjecture 5 as open for prime powers k≥4k\ge4, and even notes only computer confirmation for k≤4k\le4, n≤5n\le5; the proposed K3,3−eK_{3,3}-e example has n=6n=6. Searches for the exact formula, “linear color function”, “DP color function”, “Conjecture 5”, K3,3−eK_{3,3}-e, and the distinctive numbers 384/388 did not reveal an existing source.

      Citation: No prior citation found for the counterexample. Background conjecture: Samantha L. Dahlberg, Hemanshu Kaul, Jeffrey A. Mudrock, “A Polynomial Method for Counting Colorings of Sparse Graphs,” arXiv:2312.11744v2, Conjecture 5.

      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.