Jul 23, 2016
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.
International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Presentations on similar topic, category or speaker