The dimension of orthogonal representations

by · Jul 23, 2016 · 516 views ·

We want to assign a dd-dimensional unit vector to each node of a graph, so that non-adjacent nodes should be labeled by orthogonal vectors. In what dimension can we do so? The answer seems to be more interesting when we impose various kinds of non-degeneracy conditions. For example, if we want the representing vectors to be in general position (every dd of them linearly independent), then a rather old theorem of Saks, Schrijver and Lovasz says that this can be done if and only if the graph is (n−d)(n−d)-connected. We survey several nondegeneracy conditions, including ''transversality`` (a.k.a. Strong Arnold Property). The methods lead to a study of the algebraic variety of all orthogonal representations of a given graph in a given dimension. We characterize when this variety is irreducible up to dimension 4.

Watch SlidesLive on mobile devices

© SlidesLive Inc.