Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without K₅ minors

DOI10.1016/J.LAA.2016.07.026MaRDI QIDQ314769zbMATH OpenOpenAlexFDO

Authors Liam Solus, Caroline Uhler, Ruriko Yoshida

Publication date 16 September 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2016.07.026

zbMATH Keywords

cut polytopeelliptopeextremal matrixgraphs without \(K_5\) minorsseries-parallel graphsparsity order

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Recommendations

• Extermal positive semidefinite matrices with given sparsity pattern
• The Ranks of Extremal Positive Semidefinite Matrices with Given Sparsity Pattern
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• Positive semidefinite matrices with a given sparsity pattern
• Sparsity Patterns with High Rank Extremal Positive Semidefinite Matrices
• Completely positive matrices of order \(5\) with a nearly \(\widehat{CP} \)-graph
• Graphs whose positive semi-definite matrices have nullity at most two
• On the maximum positive semi-definite nullity and the cycle matroid of graphs
• Spanning cycles in regular matroids without \(M^{*}(K_{5})\) minors
• Characterizing graphs with fully positive semidefinite \(Q\)-matrices

Cites work

• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• Extremal bipartite matrices
• Generic Spectrahedral Shadows
• Geometry of cuts and metrics
• Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry
• On a positive semidefinite relaxation of the cut polytope
• On the cut polytope
• On the sparsity order of a graph and its deficiency in chordality
• Positive semidefinite matrices with a given sparsity pattern
• Regular and semi-regular polytopes. III
• Some geometric results in semidefinite programming
• Sparsity Patterns with High Rank Extremal Positive Semidefinite Matrices
• The Ranks of Extremal Positive Semidefinite Matrices with Given Sparsity Pattern
• The real positive definite completion problem for a simple cycle
• The real positive definite completion problem: cycle completability
• The real positive semidefinite completion problem for series-parallel graphs
• polymake: a framework for analyzing convex polytopes

Cited in

(6)

• Graphs with sparsity order at most two: the complex case
• Do sums of squares dream of free resolutions?
• Extremal rays and duals for cones of positive definite matrices with prescribed zeros
• Extermal positive semidefinite matrices with given sparsity pattern
• On the sparsity order of a graph and its deficiency in chordality
• SPN graphs

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors

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