The dimension of orthogonal representations

Jul 23, 2016

Sprecher:innen

Über

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.

Organisator

Kategorien

Über The Mathematics of Jiří Matoušek

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

Präsentation speichern

Soll diese Präsentation für 1000 Jahre gespeichert werden?

Wie speichern wir Präsentationen?

Ewigspeicher-Fortschrittswert: 0 = 0.0%

Freigeben

Empfohlene Videos

Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind

Interessiert an Vorträgen wie diesem? The Mathematics of Jiří Matoušek folgen