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

 

Abstract:
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

 

Abstract:
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

 

Abstract:
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 Florida can help you in trying times, but be sure to know the laws necessary for your loan application. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.