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

It meets ρ⊥(G)>ρ⊥(Vc)\rho^{\perp}(G)>\rho^{\perp}(V_{c}) if it meets the following: - ρ⊥(Vc)>ρ⊥(A)\text{- }\rho^{\perp}\left(V_{c}\right)>\rho^{\perp}(A) - ρ⊥(Vc)>ρ⊥(B)\text{- }\rho^{\perp}\left(V_{c}\right)>\rho^{\perp}(B) - ρ⊥(Vc)≤ρ⊥(A)+ρ⊥(B)\text{- }\rho^{\perp}\left(V_{c}\right)\leq \rho^{\perp}(A)+\rho^{\perp}(B)

Context

Candidate 8 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 a finite simple graph GG, let VcV_c be an independent vertex cut in Gˉ\bar G, and let A,BA,B be the two components of Gˉ−Vc\bar G-V_c. The conjecture claims that

    ρ⊥(G)>ρ⊥(G[Vc])\rho^\perp(G)>\rho^\perp(G[V_c])

    whenever

    ρ⊥(G[Vc])>ρ⊥(G[A]),ρ⊥(G[Vc])>ρ⊥(G[B]),ρ⊥(G[Vc])≤ρ⊥(G[A])+ρ⊥(G[B]).\rho^\perp(G[V_c])>\rho^\perp(G[A]),\quad \rho^\perp(G[V_c])>\rho^\perp(G[B]),\quad \rho^\perp(G[V_c])\le \rho^\perp(G[A])+\rho^\perp(G[B]).

    Here ρ⊥\rho^\perp is the real faithful/projective orthogonal rank used in the paper: vertices are assigned distinct non-proportional nonzero vectors, and adjacency is exactly orthogonality.

    Result: The conjecture is false.

    Let GG have vertex partition

    A={a0,a1,a2,a3},B={b1,b2,b3},Vc={c1,c2,c3,c4}.A=\{a_0,a_1,a_2,a_3\},\quad B=\{b_1,b_2,b_3\},\quad V_c=\{c_1,c_2,c_3,c_4\}.

    Define GG by the following faithful representation in R4\mathbb R^4:

    a0=e1,a1=e1+e2,a2=e1−e2,a3=e1+2e2,b1=e3+e4,b2=e3−e4,b3=e3+2e4,c1=e1+e3,c2=e1−e3,c3=e2+e4,c4=e2−e4.\begin{aligned} a_0&=e_1,& a_1&=e_1+e_2,& a_2&=e_1-e_2,& a_3&=e_1+2e_2,\\ b_1&=e_3+e_4,& b_2&=e_3-e_4,& b_3&=e_3+2e_4,\\ c_1&=e_1+e_3,& c_2&=e_1-e_3,& c_3&=e_2+e_4,& c_4&=e_2-e_4. \end{aligned}

    Put an edge exactly when the corresponding dot product is 00.

    Then VcV_c induces K4K_4, so

    ρ⊥(G[Vc])=4.\rho^\perp(G[V_c])=4.

    Also G[A]G[A] and G[B]G[B] each contain exactly one edge plus isolated vertices, hence each has faithful orthogonal rank 22:

    ρ⊥(G[A])=ρ⊥(G[B])=2.\rho^\perp(G[A])=\rho^\perp(G[B])=2.

    Thus the conjecture’s hypotheses hold:

    4>2,4>2,4≤2+2.4>2,\qquad 4>2,\qquad 4\le 2+2.

    But the displayed vectors give a faithful orthogonal representation of all of GG in R4\mathbb R^4, so ρ⊥(G)≤4\rho^\perp(G)\le4. Since GG contains the clique K4=G[Vc]K_4=G[V_c], every faithful orthogonal representation needs dimension at least 44. Therefore

    ρ⊥(G)=4=ρ⊥(G[Vc]),\rho^\perp(G)=4=\rho^\perp(G[V_c]),

    contradicting the conjectured strict inequality.

    Moreover, the cut-set context is satisfied: in Gˉ\bar G, VcV_c is independent, Gˉ−Vc\bar G-V_c has precisely the two connected components AA and BB, and Gˉ\bar G is even 44-connected, with VcV_c a vertex cut.

    Citation: No known prior disproof is being invoked; this is an explicit counterexample to Conjecture 5.2 of Solís Encina–Portillo, “Orthogonal Representation of Graphs,” arXiv:1504.03662.

    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 attacks the correct Conjecture 5.2. The displayed vectors define a faithful orthogonal representation in R4\mathbb R^4. They make VcV_c a K4K_4, so ρ⊥(Vc)=4\rho^\perp(V_c)=4; AA and BB each induce one edge plus isolated vertices, so each has faithful orthogonal rank 22. Thus the three hypotheses hold.

      Since the same vectors represent all of GG in dimension 44, while the K4K_4 forces dimension at least 44, ρ⊥(G)=4=ρ⊥(Vc)\rho^\perp(G)=4=\rho^\perp(V_c), contradicting the conjectured strict inequality. The complement cut-set condition is also satisfied. I found no evidence of a prior published disproof in the accessible literature/search results.

      Novelty assessment

      TYPE1

      Classification rationale: This appears to be a genuinely new explicit counterexample, but it is a minor contribution. It refutes a specific conjecture from an obscure 2015 “working in progress” arXiv note, using a small constructed faithful orthogonal representation. The result is useful as a correction/erratum-style observation, but unlikely to support a standalone combinatorics paper.

      Literature check: I found no prior published or online disproof of Conjecture 5.2. Searches by exact title, arXiv ID 1504.03662, author names, “Conjecture 5.2,” “rho^\perp,” and related faithful/orthogonal-rank terminology led back essentially to the original arXiv preprint and the author’s GitHub repository for associated code. GitHub repository/issue/discussion searches showed no existing counterexample or discussion. I found no stronger known theorem implying this counterexample.

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

      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.