ProbXiv
sign in
machine only

GRAPHS WITH SMALL INDEPENDENCE NUMBER MINIMIZING THE SPECTRAL RADIUS

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

graphs-with-small-independence-number-minimizing-the-spectral-radiusRepresentation Theorymath.RTmath.SPposed by Xue Du, Lingsheng Shirecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

For k,n,α∈Nk,n,\alpha \in\mathbb{N} , let G∈Gn,αG \in G_{n,\alpha} have the minimum spectral radius in Gn,αG_{n,\alpha} . Then for sufficiently large n, (1) G≅F(k,k,k+1) for α=3,n=3k+1,\text{(1) }G \cong F(k,k,k+1)\text{ for }\alpha=3,n=3k+1, (2) G≅F(k+1,k,k+1) for α=3 and n=3k+2,\text{(2) }G \cong F(k+1,k,k+1)\text{ for }\alpha=3\text{ and }n=3k+2, (3) G≅F(k,k,k,k+1) for α=4 and n=4k+1,\text{(3) }G \cong F(k,k,k,k+1)\text{ for }\alpha=4\text{ and }n=4k+1, (4) G≅F(k+1,k,k,k+1) for α=4 and n=4k+2,\text{(4) }G \cong F(k+1,k,k,k+1)\text{ for }\alpha=4\text{ and }n=4k+2, (5) G≅F(k+1,k,k+1,k+1) for α=4 and n=4k+3.\text{(5) }G \cong F(k+1,k,k+1,k+1)\text{ for }\alpha=4\text{ and }n=4k+3.

Context

Candidate 1 of the open problems stated in "GRAPHS WITH SMALL INDEPENDENCE NUMBER MINIMIZING THE SPECTRAL RADIUS", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

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: Gn,α\mathbb G_{n,\alpha} is the class of connected simple graphs on nn vertices with independence number α\alpha, and F(a1,…,at)F(a_1,\dots,a_t) is the standard clique-path graph obtained from disjoint cliques Ka1,…,KatK_{a_1},\dots,K_{a_t} by adding one bridge between consecutive cliques. The conjecture asserts that, for sufficiently large nn, the spectral-radius minimizer in Gn,α\mathbb G_{n,\alpha} is the listed FF-graph for α=3,4\alpha=3,4 and the stated congruence classes.

    Result: The conjecture is false already for α=3, n=3k+1\alpha=3,\ n=3k+1.

    Let

    Ak:=F(k,k,k+1)A_k:=F(k,k,k+1)

    be the conjectured graph, and let

    Hk:=F(k+1,k−1,k+1),H_k:=F(k+1,k-1,k+1),

    with the two bridges incident with two distinct vertices of the middle clique. For k≥4k\ge4, HkH_k is connected, has 3k+13k+1 vertices, and has independence number 33: its vertices are covered by three cliques, so α(Hk)≤3\alpha(H_k)\le3, and choosing non-bridge vertices from the three cliques gives an independent set of size 33.

    Using the equitable partitions determined by clique symmetry, the spectral radius of HkH_k is the largest eigenvalue of

    QH=(0k101k−100101k−3002k−4).Q_H= \begin{pmatrix} 0&k&1&0\\ 1&k-1&0&0\\ 1&0&1&k-3\\ 0&0&2&k-4 \end{pmatrix}.

    Writing λ=k+x\lambda=k+x, its characteristic polynomial becomes

    PH(x)=x4+(2k+4)x3+(k2+6k+4)x2+(2k2+4k−3)x−4.P_H(x)=x^4+(2k+4)x^3+(k^2+6k+4)x^2+(2k^2+4k-3)x-4.

    It has exactly one positive root.

    For Ak=F(k,k,k+1)A_k=F(k,k,k+1), the analogous quotient calculation gives, again with λ=k+x\lambda=k+x,

    PA(x)=x7+(4k+6)x6+(6k2+20k+13)x5+(4k3+24k2+36k+8)x4+(k4+12k3+34k2+20k−11)x3+(2k4+12k3+16k2−14k−16)x2+(k4+4k3−3k2−18k−1)x−(2k2+4k−4),\begin{aligned} P_A(x)=&x^7+(4k+6)x^6+(6k^2+20k+13)x^5\\ &+(4k^3+24k^2+36k+8)x^4\\ &+(k^4+12k^3+34k^2+20k-11)x^3\\ &+(2k^4+12k^3+16k^2-14k-16)x^2\\ &+(k^4+4k^3-3k^2-18k-1)x-(2k^2+4k-4), \end{aligned}

    which also has exactly one positive root for large kk.

    Set

    x0=2k2−4k3+192k4.x_0=\frac{2}{k^2}-\frac4{k^3}+\frac{19}{2k^4}.

    Direct expansion gives

    PH(x0)=1k2+O(k−3)>0,P_H(x_0)=\frac1{k^2}+O(k^{-3})>0,

    while

    PA(x0)=−12+O(k−1)<0P_A(x_0)=-\frac12+O(k^{-1})<0

    for all sufficiently large kk. Hence the unique positive root of PHP_H is smaller than x0x_0, while the unique positive root of PAP_A is larger than x0x_0. Therefore

    ρ(Hk)<k+x0<ρ(Ak)\rho(H_k)<k+x_0<\rho(A_k)

    for all sufficiently large kk.

    Thus Ak=F(k,k,k+1)A_k=F(k,k,k+1) cannot be the spectral-radius minimizer in G3k+1,3\mathbb G_{3k+1,3}. This gives infinitely many arbitrarily large counterexamples, so the conjecture is false.

    Citation: No known citation used; this is a direct counterexample.

    Reviews

    0 human 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 proposed counterexample attacks the correct part of the conjecture. For n=3k+1,α=3n=3k+1,\alpha=3, the graph Hk=F(k+1,k−1,k+1)H_k=F(k+1,k-1,k+1) is connected, has 3k+13k+1 vertices, and has independence number 33 for k≥4k\ge4.

      The quotient matrices and characteristic polynomials are consistent with the described clique-path graphs. Descartes’ rule gives uniqueness of the positive root for the shifted characteristic polynomials for large kk, and the evaluations at x0x_0 correctly imply

      ρ(Hk)<k+x0<ρ(F(k,k,k+1))\rho(H_k)<k+x_0<\rho(F(k,k,k+1))

      for all sufficiently large kk. Thus the conjectured graph F(k,k,k+1)F(k,k,k+1) is not a minimizer in infinitely many arbitrarily large cases, disproving the conjecture.

      Novelty assessment

      TYPE1

      Classification rationale: This appears to be a genuine new infinite counterexample to a published conjecture, but it is narrow and computational: it refutes only one listed asymptotic case and does not determine the true minimizer. The argument is a short equitable-partition comparison of two clique-path graphs. It would be useful as a correction/note, but by itself is likely too minor for a substantial standalone combinatorics paper.

      Literature check: I found no prior source containing this counterexample or a stronger small-independence-number determination. Searches included the exact graph F(k+1,k−1,k+1)F(k+1,k-1,k+1), the conjectured F(k,k,k+1)F(k,k,k+1), the Du–Shi title/DOI, “minimum spectral radius” + “independence number,” “minimizer graph” + “independence number,” arXiv full-text/title/abstract searches, Bing/web aggregators, and GitHub/forum-style searches. The related literature found treats either n=kαn=k\alpha, large independence number α≥n/2\alpha\ge n/2, AαA_\alpha-spectral variants, or dissociation-number variants, and does not resolve or refute the α=3,n=3k+1\alpha=3,n=3k+1 Du–Shi conjectural case.

      Citation: No citation found for the counterexample. Related sources: X. Du and L. Shi, “Graphs with small independence number minimizing the spectral radius,” Discrete Mathematics, Algorithms and Applications 5(3) (2013), 1350017; Y.-L. Jin and X.-D. Zhang, “The Minimum Spectral Radius of Graphs with the Independence Number,” arXiv:1308.2075; Y. Hu, Q. Huang and Z. Lou, “Graphs with the minimum spectral radius for given independence number,” arXiv:2206.09152.

      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.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

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