ProbXiv
sign in
machine only

A family of non-Cayley cores based on vertex-transitive or strongly regular self-complementary graphs

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.

a-family-of-non-cayley-cores-based-on-vertex-transitive-or-strongly-2Spectral Theorymath.COmath.SPposed by Marko Orelrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

It would be interesting to know if there exists a regular/vertex-transitive self-complementary graph Γ\Gamma on nn vertices with the second eigenvalue in the bounds n(n−4)−12<λ2≤n−72−2cos⁡(π(n−1)n)\frac{\sqrt{n(n-4)}-1}{2} < \lambda_2 \le \frac{n-7}{2} - 2\cos\left(\frac{\pi(n-1)}{n}\right).

Context

Candidate 2 of the open problems stated in "A family of non-Cayley cores based on vertex-transitive or strongly regular self-complementary graphs", 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: In the category of finite simple undirected graphs, let Γ\Gamma be a regular self-complementary graph on nn vertices, with adjacency eigenvalues

    λ1≥λ2≥⋯≥λn.\lambda_1\ge \lambda_2\ge \cdots \ge \lambda_n .

    Equivalently, one may ask the same for vertex-transitive self-complementary graphs; this is weaker since vertex-transitive graphs are regular. The question is whether there exists such a Γ\Gamma with

    n(n−4)−12<λ2≤n−72−2cos⁡ ⁣(π(n−1)n).\frac{\sqrt{n(n-4)}-1}{2}<\lambda_2 \le \frac{n-7}{2}-2\cos\!\left(\frac{\pi(n-1)}{n}\right).

    The reconstruction is supported by the paper’s surrounding text, which explicitly defines λ2\lambda_2 as the second adjacency eigenvalue.

    Result: No such graph exists.

    Proof. Let Γ\Gamma be a regular self-complementary graph on n>1n>1 vertices. Its degree is

    d=n−12,d=\frac{n-1}{2},

    so n≡1(mod4)n\equiv 1\pmod 4. Hence either n=5n=5 or n≥9n\ge 9.

    For n=5n=5,

    5−12=5−72−2cos⁡ ⁣(4π5),\frac{\sqrt{5}-1}{2} = \frac{5-7}{2}-2\cos\!\left(\frac{4\pi}{5}\right),

    so the interval is empty because the lower inequality is strict.

    Now assume n≥9n\ge 9. Let AA be the adjacency matrix. Since Γ≅Γ‾\Gamma\cong \overline{\Gamma}, the nontrivial eigenvalues are invariant under

    λ↦−1−λ.\lambda\mapsto -1-\lambda .

    Thus

    λn=−1−λ2.\lambda_n=-1-\lambda_2.

    Also

    ∑i=1nλi2=tr⁡(A2)=nd,\sum_{i=1}^n \lambda_i^2=\operatorname{tr}(A^2)=nd,

    so

    ∑i=2nλi2=nd−d2=n2−14.\sum_{i=2}^n \lambda_i^2 =nd-d^2 =\frac{n^2-1}{4}.

    Therefore

    n2−14≥λ22+λn2=λ22+(λ2+1)2.\frac{n^2-1}{4} \ge \lambda_2^2+\lambda_n^2 =\lambda_2^2+(\lambda_2+1)^2.

    Let

    L=n(n−4)−12.L=\frac{\sqrt{n(n-4)}-1}{2}.

    If λ2>L\lambda_2>L, then

    λ22+(λ2+1)2>L2+(L+1)2=n(n−4)+12.\lambda_2^2+(\lambda_2+1)^2 > L^2+(L+1)^2 = \frac{n(n-4)+1}{2}.

    But for n≥9n\ge 9,

    n(n−4)+12−n2−14=n2−8n+34>0,\frac{n(n-4)+1}{2}-\frac{n^2-1}{4} = \frac{n^2-8n+3}{4}>0,

    a contradiction. Hence no regular self-complementary graph satisfies the lower bound, and therefore none satisfies the stated two-sided bounds.

    Since every vertex-transitive graph is regular, this also rules out the vertex-transitive interpretation.

    Verification audit: The proof uses only regularity and self-complementarity, so it covers both plausible meanings of “regular/vertex-transitive.” The n=5n=5 endpoint is checked separately, and for n≥9n\ge 9 the lower bound alone is impossible.

    Citation: No prior resolution is used here. The proof relies only on elementary adjacency-spectrum identities, standard for regular graphs and graph complements.

    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 proof correctly attacks the stated existence question. The spectral pairing for regular self-complementary graphs gives λn=−1−λ2\lambda_n=-1-\lambda_2, and the trace-square identity yields

      λ22+(λ2+1)2≤(n2−1)/4.\lambda_2^2+(\lambda_2+1)^2\le (n^2-1)/4.

      If λ2>(n(n−4)−1)/2\lambda_2>(\sqrt{n(n-4)}-1)/2, this contradicts that bound for all n≥9n\ge 9; n=5n=5 is handled separately with an empty interval. Thus no regular, hence no vertex-transitive, self-complementary graph satisfies the required bounds.

      Novelty assessment

      TYPE1

      Classification rationale: The resolution is an elementary one-line spectral bound once the standard facts are recalled. For a regular self-complementary graph, the nontrivial eigenvalues pair under λ↦−1−λ\lambda\mapsto -1-\lambda, and ∑iλi2=2∣E∣\sum_i\lambda_i^2=2|E|. This immediately gives an upper bound on λ2\lambda_2 below Orel’s lower threshold for n≥9n\ge 9, with n=5n=5 trivial. This is useful as a correction/observation about the remark, but far too short and routine for a standalone paper.

      Literature check: I found no explicit prior statement resolving Orel’s Remark 2.35 or the exact interval question. Searches for the exact bound n(n−4)\sqrt{n(n-4)}, for “regular/vertex-transitive self-complementary graph second eigenvalue”, and related phrases led back to Orel’s paper or to standard spectral-graph references. The ingredients themselves are standard and already cited/used around Orel’s discussion: complement spectra of regular graphs and the trace-square identity for adjacency matrices.

      Citation: No prior exact resolution found. Standard background: A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, 2012; Marko Orel, A family of non-Cayley cores based on vertex-transitive or strongly regular self-complementary graphs, arXiv:2110.10416, Remark 2.35.

      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.