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

DOI10.1007/S10107-013-0648-XMaRDI QIDQ2248754zbMATH OpenOpenAlexFDO

Authors Monique Laurent, A. Varvitsiotis

Publication date 27 June 2014

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

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

zbMATH Keywords

combinatorial matrix theoryEuclidean distance matrixgeometric graph representationgraph minorgraph realizabilitymatrix completionsemidefinite programming

Mathematics Subject Classification ID

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

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}.

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

Cites work

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

Cited in

(20)

• Typical ranks in symmetric matrix completion
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
• Unavoidable minors for graphs with large \(\ell_p\)-dimension
• 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
• Determinantal sampling designs
• Universal completability, least eigenvalue frameworks, and vector colorings
• Complexity of the positive semidefinite matrix completion problem with a rank constraint
• Selected open problems in discrete geometry and optimization
• The Gram dimension of a graph
• Graph cores via universal completability
• Critical Graphs for the Positive Definite Completion Problem
• Do sums of squares dream of free resolutions?
• Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
• Singularity degree of the positive semidefinite matrix completion problem
• On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem
• A new algorithm for positive semidefinite matrix completion
• Realizable dimension of periodic frameworks
• Finite-rank kernel realization and completion

Describes a project that uses

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)