9
$\begingroup$

A faithful orthonormal representation of a graph $G=(V,E)$ on $n$ vertices $\{1,2,\dotsc,n\}$ is an assignment of unit vectors $v_1,v_2,...,v_n \in \mathbb{R}^d$ to the vertices of $G$ such that $\langle v_i,v_j \rangle =0 \Leftrightarrow ij \in E(G)$, and in addition $|\langle v_i , v_j \rangle| \neq 1$ if $i \neq j$, i.e., distinct vertices are assigned non-parallel vectors. Note that this definition of orthonormal representation is slightly rarer in the literature and differs (by graph complementation) from the definition in [1] where $ij \in E(\bar{G}) \Rightarrow \langle v_i , v_j \rangle = 0$.

The question is: Given a graph $G$ that has a faithful orthonormal representation in dimension $d$, form a new graph $G'$ by deleting an edge $uv$ from $G$. Does $G'$ then also have a faithful orthonormal representation in the same dimension $d$?

[1] L. Lovász, On the Shannon Capacity of a Graph, IEEE Trans. Inf. Theory, 25 (1):1-7 (1979).

Improve this question
$\endgroup$
3
  • $\begingroup$ It seems useful to point out: because of the interestingly unusual (compared to some relevant articles) additional condition $\lvert\langle v_i,v_j\rangle\rvert=1\to i=j$ in the OP, it seems that a more appropriate mathematical concept to use is lines through the origin in $\mathbb{R}^d$. I.e., the suggestion is to represent vertices by lines through the origin, whereupon (this is the point) the condition of distinctness automatically implies the additional condition of non-parallelness. However, I would not recommend replacing the current formulation by this, only augmenting [...] $\endgroup$
    – Peter Heinig
    Commented Oct 13, 2017 at 10:11
  • $\begingroup$ [...] the current OP with this alternative formulation. Explicitly, you could write: "Equivalently, let a $d$-dimensional f.o.r. of a graph $G=(n,E)$ mean an $n$-set $\{L_0,\dotsc,L_{n-1}\}$ of lines through the origin in $\mathbb{R}^d$ such that $ij\in E\ \Leftrightarrow\ $ $L_i\perp L_j$. (Here, $\perp$ means 'orthogonal')" (I could not escape my preference for indexing from $0$ to $n-1$ here; the main advantage here is the brevity with which one can make the problem statement precise by writing $G=(n,E)$, where $n$ denotes the finite ordinal $\{0,1,\dotsc,n-1\}$. Just a suggestion.) $\endgroup$
    – Peter Heinig
    Commented Oct 13, 2017 at 10:16
  • $\begingroup$ In dimension 3 or more, I would try the following example: consider directions of all integer vectors in $[-N,N]^d$ for large $N$. Many of them are orthogonal, and it looks quite a rigid construction, that is, removing one edge from the orthogonality graph we should still have the same configuration. $\endgroup$
    – Fedor Petrov
    Commented Oct 13, 2017 at 10:59

2 Answers 2

Reset to default
4
$\begingroup$

The following would be a counterexample if we require only $v_i \ne v_j$ but don't forbid different vertices to become antipodes on the sphere. Let us call this a weakly faithful orthogonal representation.

The graph of the octahedron has a weakly faithful representation in (real) dimension 2, given by $\pm e_i$. If you remove one edge, there will be no faithful representation in dimension 2: the remaining edges force the two non-connected vertices to lie at distance $\pi/2$ on the sphere.

So, for faithful orthogonal representations the question is: can one force the distance (in the standard spherical metric) between two points in the projective space to be $\pi/2$ by imposing distances $\pi/2$ between some pairs of points?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much for the answer. I have a comment though: with faithful representations defined as in the question, requiring different vertices to be assigned distinct vectors, the graph of the octahedron does not appear to have a faithful representation in (real) dimension 2. $\endgroup$
    – pizzazz
    Commented Oct 10, 2017 at 19:21
  • 2
    $\begingroup$ Oh yes, different vertices are not allowed to become antipodal points on the sphere. Then my counterexample is wrong. $\endgroup$
    – Ivan Izmestiev
    Commented Oct 11, 2017 at 11:32
3
$\begingroup$

Thanks to a commenter for pointing out that the following was hasty: the fallacy is of course in the statement that the edgeless graph had no faithful orthogonal representation. I'll leave it at that, but add a warning.

No. Fallacious proof by contradiction; the red is wrong. if this were true, then, since you required the graph to be finite, iterating the (hypothetical) statement $\lvert E\rvert$-many times would lead us to the conclusion that the edgeless graph on $n$ vertices has a faithful orthogonal representation in dimension $d$, $\color{red}{\text{which is absurd}}$. This proves that the answer cannot possibly be yes.

Useful addition: the relevant technical term is monotone graph property. And the above gives a reason why

for any fixed $n$ and $d$, the property(=isomorphism-invariant class of graphs) of all those graphs which admit a faithful orthogonal representation in dimension $d$ is not a monotone decreasing graph property.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ An edgeless graph has a faithful orthogonal representation in any dimension ($>1$): take $n$ different vectors close to each other. $\endgroup$
    – Ivan Izmestiev
    Commented Oct 10, 2017 at 18:51
  • $\begingroup$ @IvanIzmestiev: many thanks for pointing out; multitasking; will edit accordingly to set the record straight. $\endgroup$
    – Peter Heinig
    Commented Oct 10, 2017 at 18:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .