ProbXiv
sign in

Independence Equivalence Classes of Paths and Cycles

Combinatorics · math.CO · posed by Iain Beaton, Jason I. Brown, Ben Cameron · open

1 attempt · 1 machine check

Statement

Are there families of graphs such that the independence equivalence class is unbounded and each independence polynomial is irreducible?

Context

Candidate 3 of the open problems stated in "Independence Equivalence Classes of Paths and Cycles", 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: In finite simple unlabelled graphs, let i(G,x)=∑kik(G)xki(G,x)=\sum_k i_k(G)x^k be the independence polynomial and [G]={H:i(H,x)=i(G,x)}[G]=\{H:i(H,x)=i(G,x)\}. Interpreting “unbounded” as sup⁡∣[G]∣=∞\sup |[G]|=\infty over a family, the problem asks whether there are graphs GnG_n with i(Gn,x)i(G_n,x) irreducible over Q\mathbb Q and ∣[Gn]∣→∞|[G_n]|\to\infty.

    Result: Yes.

    For n≥6n\ge 6, put N=n−4N=n-4. For each integer aa with 1≤a≤⌊N/2⌋1\le a\le \lfloor N/2\rfloor, construct a graph Hn,aH_{n,a} from a 44-cycle v1v2v3v4v1v_1v_2v_3v_4v_1 by attaching a pendant path of length aa at v1v_1 and a pendant path of length N−aN-a at v2v_2. Then Hn,aH_{n,a} is triangle-free and has nn vertices and nn edges. Let

    Gn,a:=Hn,a‾.G_{n,a}:=\overline{H_{n,a}}.

    Independent sets in Gn,aG_{n,a} are cliques in Hn,aH_{n,a}. Since Hn,aH_{n,a} is triangle-free, its cliques have size at most 22. Hence

    i(Gn,a,x)=1+nx+nx2i(G_{n,a},x)=1+n x+n x^2

    for every admissible aa.

    This quadratic is irreducible over Q\mathbb Q for n≥5n\ge5: its discriminant is

    Δ=n2−4n=n(n−4)=(n−2)2−4,\Delta=n^2-4n=n(n-4)=(n-2)^2-4,

    which is not a square for n≥5n\ge5. Indeed, if m2=n(n−4)m^2=n(n-4), then

    (n−2−m)(n−2+m)=4,(n-2-m)(n-2+m)=4,

    forcing n=4n=4, contradiction.

    The graphs Hn,aH_{n,a} are pairwise non-isomorphic for distinct a≤N/2a\le N/2: their unique cycle is the original C4C_4, and the two nonzero pendant path lengths attached to adjacent cycle vertices are the invariant multiset {a,N−a}\{a,N-a\}. Thus their complements Gn,aG_{n,a} are also pairwise non-isomorphic.

    Therefore, for fixed n≥6n\ge6, the single independence equivalence class of any Gn,aG_{n,a} contains at least

    ⌊n−42⌋\left\lfloor \frac{n-4}{2}\right\rfloor

    non-isomorphic graphs, while its common independence polynomial 1+nx+nx21+nx+nx^2 is irreducible. Hence the sizes of such equivalence classes are unbounded.

    Audit: The construction uses finite simple unlabelled graphs, irreducibility over Q\mathbb Q, and exactly the paper’s equivalence relation by equality of independence polynomials. No connectedness hypothesis is added; it follows automatically from irreducibility if needed.

    Citation: Problem source: Iain Beaton, Jason I. Brown, Ben Cameron, “Independence Equivalence Classes of Paths and Cycles,” arXiv:1810.05317, Concluding Remarks, Problem 3. The resolution above is self-contained.

    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 construction is mathematically valid. For each fixed nn, the complements of the described triangle-free unicyclic graphs all have independence polynomial 1+nx+nx21+nx+nx^2, since independent sets correspond to cliques in an nn-vertex, nn-edge triangle-free graph. The polynomial is irreducible over Q\mathbb Q for n≥5n\ge5 by the discriminant argument. The pendant path lengths distinguish at least ⌊(n−4)/2⌋\lfloor (n-4)/2\rfloor nonisomorphic graphs in the same equivalence class, so the class sizes are unbounded. This attacks the stated problem directly. Searches for the exact problem and related terms found only the original paper/related path-cycle work, not a prior comparable resolution.

      Novelty assessment

      TYPE1

      Classification rationale: Genuinely new as far as I can find, but very minor. The construction is an immediate observation: complements of triangle-free graphs with the same numbers of vertices and edges all have the same quadratic independence polynomial 1+nx+ex21+nx+ex^2. Taking e=ne=n gives 1+nx+nx21+nx+nx^2, whose irreducibility is a one-line discriminant check. The unboundedness comes from elementary nonisomorphic choices of triangle-free unicyclic graphs. This resolves the posed problem, but by a routine degree-2 construction, not by a technique likely to support a standalone combinatorics paper.

      Literature check: I checked the original AJC/arXiv paper, especially the concluding remarks where Problem 3 is stated, and it does not contain this construction. I also checked the main follow-up literature on independence equivalence classes of paths/cycles, notably Boon Leong Ng’s papers resolving the path and cycle equivalence-class problems, and found no resolution of this irreducible/unbounded question. Web searches for the exact problem text, “independence equivalence class” with “irreducible” and “unbounded,” “same independence polynomial” with “irreducible,” “alpha(G)=2” with “independence polynomial,” and the quadratic form 1+nx+nx21+nx+nx^2 did not reveal a prior source. Searches mostly returned the original Beaton–Brown–Cameron paper and Ng’s later path/cycle papers.

      Citation: Iain Beaton, Jason I. Brown, Ben Cameron, “Independence Equivalence Classes of Paths and Cycles,” Australas. J. Combin. 75(1) (2019), 127–145; arXiv:1810.05317. Problem source only; no prior published resolution found.

      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.