A new graph parameter related to bounded rank positive semidefinite matrix completions

DOI10.1007/S10107-013-0648-XzbMATH Open1293.05238arXiv1204.0734OpenAlexW2024448984MaRDI QIDQ2248754FDOQ2248754

A. Varvitsiotis, Monique Laurent

Publication date: 27 June 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: The Gram dimension $gd(G)$ of a graph $G$ is the smallest integer $kge1$ such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of $G$, can be completed to a positive semidefinite matrix of rank at most $k$ (assuming a positive semidefinite completion exists). For any fixed $k$ the class of graphs satisfying $gd(G)lek$ is minor closed, hence it can characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is $K_{k+1}$ for $kle3$ and that there are two minimal forbidden minors: $K_5$ and $K_{2,2,2}$ for $k=4$. We also show some close connections to Euclidean realizations of graphs and to the graph parameter $u^{=}(G)$ of cite{H03}. In particular, our characterization of the graphs with $gd(G)le4$ implies the forbidden minor characterization of the 3-realizable graphs of Belk and Connelly cite{Belk,BC} and of the graphs with $u^{=}(G)le4$ of van der Holst cite{H03}.

Full work available at URL: https://arxiv.org/abs/1204.0734

Recommendations

• The Gram dimension of a graph
• Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
• The real positive semidefinite completion problem for series-parallel graphs
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
• The minimum semidefinite rank of the complement of partial \(k\)-trees

zbMATH Keywords

matrix completionsemidefinite programmingEuclidean distance matrixgraph minorcombinatorial matrix theorygraph realizabilitygeometric graph representation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Matrix completion problems (15A83) Semidefinite programming (90C22) Graph representations (geometric and intersection representations, etc.) (05C62) Graph minors (05C83)

Cites Work

• Maximum stable set formulations and heuristics based on continuous optimization
• Matrix Analysis
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Convex Analysis
• On the Shannon capacity of a graph
• Graph minors. XX: Wagner's conjecture
• Geometry of cuts and metrics
• Euclidean distance matrices, semidefinite programming and sensor network localization
• Positive definite completions of partial Hermitian matrices
• Embedded in the Shadow of the Separator
• Sum of squares method for sensor network localization
• Multiplicities of eigenvalues and tree-width of graphs
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• The real positive definite completion problem for a simple cycle
• The real positive semidefinite completion problem for series-parallel graphs
• The minimum rank of symmetric matrices described by a graph: a survey
• Topology of series-parallel networks
• Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Forbidden minors characterization of partial 3-trees
• Solving Euclidean distance matrix completion problems via semidefinite progrmming
• Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian
• Title not available (Why is that?)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Orthogonal representations, minimum rank, and graph complements
• A remark on the rank of positive semidefinite matrices subject to affine constraints
• Euclidean Distance Matrices and Applications
• Two tree-width-like graph invariants
• Realizability of graphs
• The rotational dimension of a graph
• Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems
• A semidefinite programming approach to tensegrity theory and realizability of graphs
• Realizability of graphs in three dimensions
• The Gram Dimension of a Graph

Cited In (16)

• Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint
• Typical ranks in symmetric matrix completion
• Determinantal sampling designs
• Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
• Sums of squares and quadratic persistence on real projective varieties
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
• Selected Open Problems in Discrete Geometry and Optimization
• Graph cores via universal completability
• On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem
• Do Sums of Squares Dream of Free Resolutions?
• Unavoidable minors for graphs with large \(\ell_p\)-dimension
• Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
• Universal completability, least eigenvalue frameworks, and vector colorings
• A new algorithm for positive semidefinite matrix completion
• Critical Graphs for the Positive Definite Completion Problem

Uses Software

• Max-AO

This page was built for publication: A new graph parameter related to bounded rank positive semidefinite matrix completions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248754)