Invited Session Wed.2.H 2036

Wednesday, 13:15 - 14:45 h, Room: H 2036

Cluster 4: Conic programming [...]

Semidefinite programming and geometric representations of graphs


Chair: Monique Laurent and Christoph Helmberg



Wednesday, 13:15 - 13:40 h, Room: H 2036, Talk 1

Susanna Reiss
Optimizing extremal eigenvalues of the weighted Laplacian of a graph

Coauthors: Frank Göring, Christoph Helmberg


We study connections between the eigenspaces of the graph's Laplacian and graph properties. For this purpose, we analyze optimal solutions of minw{ λ max(Lw(G))- λ 2(Lw(G))}, by semidefinite programming techniques, i.e., we optimize nonnegative edge weights w of a graph, that sum up to one, so as to minimize the difference of the maximum and the second smallest eigenvalue of the corresponding weighted Laplacian Lw(G). The dual program may be interpreted as a graph realization problem in Euclidean space, that reflects the optimized eigenspaces. We present connections between structural properties of the graph (especially its separator structure) and geometrical properties of optimal graph realizations, thereby shedding light on relations between the graph's properties and its eigenvectors. Furthermore we are able to prove the existence of optimal graph realizations whose dimensions are bounded by the tree-width of the graph plus one.



Wednesday, 13:45 - 14:10 h, Room: H 2036, Talk 2

Marcel Kenji de Carli Silva
Optimization problems over unit-distance representations of graphs

Coauthor: Levent Tuncel


We start with a result of Lovász relating the theta number of a graph to its smallest radius hypersphere embedding where each edge has unit length. We use this identity and its generalizations to establish close relationships among many related graph parameters. We then study the more general problem of finding the smallest radius of an ellipsoid of a given shape that contains an embedding of a given graph where each edge has unit length.
This talk is based on joint work with Levent Tunçel.



Wednesday, 14:15 - 14:40 h, Room: H 2036, Talk 3

Antonios Varvitsiotis
Two new graph parameters related to semidefinite programming with a rank constraint

Coauthors: Marianna Eisenberg-Nagy, Monique Laurent


We consider geometric representations of edge weighted graphs
obtained by assigning unit vectors to the nodes, such that the
weight of each edge is equal to the inner product of the vectors
assigned to its endpoints. We introduce two new graph parameters
related to the minimum dimension where such representations exist.
Their study is motivated by their relevance to bounded rank
positive semidefinite matrix completions and to the graphical
Grothendieck problem with a rank constraint.

In this talk we analyze combinatorial and geometric properties of
these parameters.
In particular, we provide forbidden minor characterizations as well
as structural and complexity results. Additionally, we discuss how
our results imply some known characterizations of parameters
related to Euclidean graph realizations and Colin de
Verdière-type graph invariants.


  Payday Loans In Virginia. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.