The dimension of orthogonal representations

Jul 23, 2016

Speakers

About

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.

Organizer

Categories

About The Mathematics of Jiří Matoušek

International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow The Mathematics of Jiří Matoušek