ProbXiv
sign in

Working in progress: Orthogonal Representation of Graphs

Algebra · math.CO · math.RT · posed by Alberto Solís Encina, Jose Ramón Portillo · open

1 attempt · 1 machine check

Statement

If G=(V, E) is self-complementary and vertice-transitive,then ρ⊥(G)=⌈n/2⌉\rho^{\perp}(G)=\lceil n/2 \rceil

Context

Candidate 5 of the open problems stated in "Working in progress: Orthogonal Representation of 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 simple graph G=(V,E)G=(V,E) with n=∣V∣n=|V|, if GG is self-complementary and vertex-transitive, then its faithful orthogonal range

    ρ⊥(G)=min⁡{d:∃f:V→Rd∖{0}, xy∈E  ⟺  ⟨f(x),f(y)⟩=0}\rho^\perp(G)=\min\{d:\exists f:V\to \mathbb R^d\setminus\{0\},\ xy\in E\iff \langle f(x),f(y)\rangle=0\}

    equals ⌈n/2⌉\lceil n/2\rceil. The paper’s definition also requires distinct vectors; the construction below satisfies the stronger condition that no two assigned vectors are proportional.

    Result: The conjecture is false.

    Let CC be the 5-cycle on Z5\mathbb Z_5 with edges i∼ji\sim j iff i−j≡±2(mod5)i-j\equiv \pm2\pmod 5. Let

    G=C[C]G=C[C]

    be the lexicographic product. Thus V(G)=Z52V(G)=\mathbb Z_5^2, and

    (i,a)∼(j,b)  ⟺  (i−j≡±2 mod 5) or (i=j and a−b≡±2 mod 5).(i,a)\sim(j,b) \iff \bigl(i-j\equiv\pm2\bmod 5\bigr) \text{ or } \bigl(i=j\text{ and }a-b\equiv\pm2\bmod 5\bigr).

    Then GG has 2525 vertices. It is vertex-transitive because translations of Z52\mathbb Z_5^2 preserve adjacency. It is self-complementary because (i,a)↦(2i,2a)(i,a)\mapsto(2i,2a) sends differences ±2\pm2 to ±1\pm1, hence maps GG isomorphically to G‾\overline G.

    Now construct a faithful orthogonal representation in R9\mathbb R^9. Put

    c2=−cos⁡(4π/5)=1+54,ε=π/13,c^2=-\cos(4\pi/5)=\frac{1+\sqrt5}{4},\qquad \varepsilon=\pi/13,

    and define

    ui=(cos⁡(2πi/5),sin⁡(2πi/5),c),u_i=(\cos(2\pi i/5),\sin(2\pi i/5),c), vi,a=(cos⁡(2πa/5+iε),sin⁡(2πa/5+iε),c),v_{i,a}=(\cos(2\pi a/5+i\varepsilon),\sin(2\pi a/5+i\varepsilon),c), xi,a=ui⊗vi,a∈R3⊗R3≅R9.x_{i,a}=u_i\otimes v_{i,a}\in \mathbb R^3\otimes\mathbb R^3\cong\mathbb R^9.

    Then

    ⟨xi,a,xj,b⟩=(cos⁡(2π(i−j)/5)+c2)(cos⁡(2π(a−b)/5+(i−j)ε)+c2).\langle x_{i,a},x_{j,b}\rangle = \bigl(\cos(2\pi(i-j)/5)+c^2\bigr) \bigl(\cos(2\pi(a-b)/5+(i-j)\varepsilon)+c^2\bigr).

    The first factor is zero exactly when i−j≡±2(mod5)i-j\equiv\pm2\pmod5. If i=ji=j, the second factor is zero exactly when a−b≡±2(mod5)a-b\equiv\pm2\pmod5. If i−j≡±1(mod5)i-j\equiv\pm1\pmod5, then i−j∈{±1,±4}i-j\in\{\pm1,\pm4\}, and the second factor cannot vanish: otherwise

    2π(a−b)/5+(i−j)π/13≡±4π/5(mod2π),2\pi(a-b)/5+(i-j)\pi/13\equiv \pm4\pi/5 \pmod{2\pi},

    which would force 5(i−j)5(i-j) to be divisible by 1313, impossible for i−j∈{±1,±4}i-j\in\{\pm1,\pm4\}.

    Hence

    ⟨xi,a,xj,b⟩=0  ⟺  (i,a)∼(j,b).\langle x_{i,a},x_{j,b}\rangle=0 \iff (i,a)\sim(j,b).

    All vectors are nonzero, and no two are proportional. Therefore

    ρ⊥(G)≤9.\rho^\perp(G)\le 9.

    But n=25n=25, so the conjectured value is

    ⌈252⌉=13.\left\lceil\frac{25}{2}\right\rceil=13.

    Thus ρ⊥(G)≠⌈n/2⌉\rho^\perp(G)\ne \lceil n/2\rceil, disproving the conjecture.

    Citation: Conjecture and notation: Alberto Solís-Encina and José Ramón Portillo, “Orthogonal Representation of Graphs,” arXiv:1504.03662, Conjecture 4.1. The counterexample 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 a valid counterexample. The graph on 2525 vertices is vertex-transitive and self-complementary, and the tensor-vector assignment in R9\mathbb R^9 has zero inner products exactly on the edges as claimed. Thus ρ⊥(G)≤9<13=⌈25/2⌉\rho^\perp(G)\le 9<13=\lceil 25/2\rceil, so the conjectured equality is false. I found no fatal gap in the proof.

      Novelty assessment

      TYPE1

      Classification rationale: The construction is a valid but very small counterexample to a low-visibility conjecture from an unpublished/working arXiv paper. It uses elementary, explicit vectors for a 25-vertex lexicographic-product graph and gives only an upper bound ρ⊥(G)≤9<13\rho^\perp(G)\le 9<13. This is mathematically useful as a correction, but not substantial enough for a standalone combinatorics-journal paper unless embedded in a broader study of faithful orthogonal representations.

      Literature check: I found no evidence that this specific counterexample, or an explicit disproof of Solís-Encina–Portillo Conjecture 4.1, is already in the literature. Searches covered the exact paper title and conjecture, the notation ρ⊥\rho^\perp, “faithful orthogonal representation” with “self-complementary” and “vertex-transitive,” “orthogonal rank”/“minimum semidefinite rank” variants, arXiv full-text/title/abstract searches, alphaXiv, GitHub, and related faithful-orthogonal-representation papers. Related literature discusses faithful orthogonal representations/minimum positive semidefinite rank, but I did not find this resolution or a stronger published statement.

      Citation: Alberto Solís-Encina and José Ramón Portillo, “Orthogonal Representation of Graphs,” arXiv:1504.03662, Conjecture 4.1.

      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.