Working in progress: Orthogonal Representation of Graphs

NEW Problem: Reconstructed statement: for finite simple graphs, let $\rho^\perp(G)$ be the least $d$ for which vertices can be assigned distinct real projective lines in $\mathbb R^d$ such that two vertices are adjacent iff their lines are orthogonal. A graph is “critical” in the paper’s literal sense if deleting any edge changes $\rho^\perp$. Interpreting “not banned” as not one of the paper’s space-monopolizing banned graphs with $\rho^\perp(G)=|V(G)|$, Conjecture 3.3 claims:

If $G$ is critical, not banned, and $\rho^\perp(G)=d$, then for a maximum matching $M$,

$$\rho^\perp(G-M)\le d-1.$$

This interpretation is supported by the paper’s examples $\rho^\perp(C_4)=4$ and $\rho^\perp(K_{m,n})=4$, which force the “distinct projective lines/no proportional vectors” reading.

Result: The conjecture is false.

Take $G=K_{3,4}$. Then $\rho^\perp(K_{3,4})=4$: the two parts must span mutually orthogonal subspaces of dimensions at least $2$ and $2$, and this is achieved in $\mathbb R^4$.

Deleting any edge gives $K_{3,4}-e$, and $\rho^\perp(K_{3,4}-e)=5$. Indeed, suppose $K_{3,4}-a_1b_1$ had a representation in $\mathbb R^4$. Since $b_2,b_3,b_4$ are all orthogonal to $a_1,a_2,a_3$, the span of the $a_i$’s has dimension at most $2$. Since $a_2,a_3$ are both orthogonal to all $b_j$’s and are not proportional, the span of the $b_j$’s also has dimension at most $2$. Hence these two $2$-spaces are orthogonal, forcing $a_1\perp b_1$, contradicting that $a_1b_1$ is the deleted edge. A $5$-dimensional representation is given by

$$a_2=e_1,\quad a_3=e_2,\quad a_1=e_1+e_2+e_3,$$ $$b_1=e_3+e_4,\quad b_2=e_4,\quad b_3=e_4+e_5,\quad b_4=e_4+2e_5.$$

Thus $K_{3,4}$ is critical in the paper’s literal sense and is not banned in the $\rho^\perp=|V|$ sense.

Let $M=\{a_1b_1,a_2b_2,a_3b_3\}$, a maximum matching. Then $G-M$ is not representable in $\mathbb R^3$: $b_4$ is adjacent to all $a_i$, so the $a_i$’s must span a subspace of dimension at most $2$. Since the three $a_i$’s are pairwise nonadjacent, they are nonproportional, so any two span that same plane. But $b_i$ must be orthogonal to the other two $a$’s and nonorthogonal to $a_i$, impossible in $\mathbb R^3$. Therefore

$$\rho^\perp(G-M)\ge4>d-1=3.$$

This contradicts Conjecture 3.3.

Citation: No prior resolution is needed; this is an explicit counterexample.