On orthogonal representations of graphs (Q1841919): Difference between revisions

A simple graph on the vertex set \(\{ 1,2, \dots ,n \}\) can be represented by \(d\)-tuples \(x_1, \ldots ,x_n\) with entries from a field \(F\) where \(x_ix_j=x_i^1x_j^1 + x_i^2x_j^2 + \cdots + x_i^dx_j^d\) is 0 if and only if \(i\) and \(j\) are nonadjacent in \(G\). For such representations, the dimension is at most \(n-1\) for general fields, and at most \(n-2\) for fields of characteristic 2 and graphs other than the \(n\)-path.