Working in progress: Orthogonal Representation of Graphs

NEW

Problem: Reconstructed statement: for every finite simple graph $G$ on $n=|V(G)|$ vertices, the faithful orthogonal representation dimension $\rho^\perp(G)$ satisfies

Here $\rho^\perp(G)$ is the least $d$ for which the vertices can be assigned distinct real projective lines in $\mathbb R^d$ such that two vertices are adjacent exactly when their assigned lines are orthogonal. The projective-line interpretation is supported by the paper’s discussion that proportional vectors are not allowed and by its claim $\rho^\perp(K_{m,n})=4$ for $m,n\ge2$. If the written definition is read literally as only requiring distinct vectors, the counterexample below remains valid, even more strongly.

Result: The conjecture is false. Let

Then $|V(G)|=14$, and $\bar G=K_7\sqcup K_7$.

First, $\rho^\perp(K_{7,7})=4$. A representation in $\mathbb R^4=\mathbb R^2\oplus\mathbb R^2$ is obtained by putting the seven vertices in one part on seven distinct nonorthogonal lines in the first $\mathbb R^2$, and the seven vertices in the other part on seven distinct nonorthogonal lines in the second $\mathbb R^2$. Cross-part lines are orthogonal, and within-part lines are not. Conversely, since each part has at least two distinct projective lines, the two parts must occupy mutually orthogonal subspaces of dimensions at least $2$ and $2$, so dimension at least $4$ is necessary.

Second, $\rho^\perp(K_7\sqcup K_7)=7$. A clique of size $7$ needs seven mutually orthogonal nonzero lines, so dimension at least $7$ is necessary. In $\mathbb R^7$, take one component represented by the standard basis lines $[e_i]$. Take the other component represented by the columns of an orthogonal $7\times7$ matrix with no zero entries, for example the Householder matrix

Its columns are mutually orthogonal, and every inner product $e_i^Tq_j$ is nonzero, so there are no unwanted cross-component orthogonalities.

Therefore

but

Thus

contradicting the lower bound. The conjecture is disproved.

Citation: No external resolution used. Conjecture source: Solís-Encina and Portillo, “Orthogonal Representation of Graphs,” arXiv:1504.03662, Conjecture 4.2.