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

@article{Laurent2014ANG, title={A new graph parameter related to bounded rank positive semidefinite matrix completions}, author={Monique Laurent and Antonios Varvitsiotis}, journal={Mathematical Programming}, year={2014}, volume={145}, pages={291-325} }

The Gram dimension $$\mathrm{gd}(G)$$ of a graph $$G$$ is the smallest integer $$k\ge 1$$ 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 $$\mathrm{gd}(G) \le k$$ is minor closed, hence it can be characterized by… Expand

#### 47 Citations

On bounded rank positive semidefinite matrix completions of extreme partial correlation matrices

- Mathematics, Computer Science
- ArXiv
- 2012

An upper bound foregd(G) is shown in terms of a new tree-width-like parameter $\sla(G), defined as the smallest $r$ for which $G$ is a minor of the strong product of a tree and $K_r$ is shown. Expand

Universal Completability, Least Eigenvalue Frameworks, and Vector Colorings

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2017

This work identifies a sufficient condition for showing that a graph is UVC based on the universal completability of an associated framework and proves that Kneser and q-Kneser graphs are UVC. Expand

Unavoidable Minors for Graphs with Large
$$\ell _p$$
ℓ
p
-Dimension

- Computer Science, Mathematics
- Discret. Comput. Geom.
- 2021

This paper characterize the minor-closed graph classes C with bounded ℓ p -dimension, and gives a simple proof that C has boundedℓ 2 -dimension if and only if $$\mathscr {C}$$C has bounded treewidth. Expand

The Signed Positive Semidefinite Matrix Completion Problem for Odd-$K_4$ Minor Free Signed Graphs

- Mathematics
- 2016

We give a signed generalization of Laurent's theorem that characterizes feasible positive semidefinite matrix completion problems in terms of metric polytopes. Based on this result, we give a… Expand

Do Sums of Squares Dream of Free Resolutions?

- Mathematics, Computer Science
- SIAM J. Appl. Algebra Geom.
- 2017

The results allow us to generalize the work of Blekherman-Smith-Velasco on equality of nonnegative polynomials and sums of squares from irreducible varieties to reduced schemes and to classify all spectrahedral cones with only rank one extreme rays. Expand

The Gram Dimension of a Graph

- Mathematics, Philosophy
- ISCO
- 2012

It is shown that a graph has Gram dimension at most 4 if and only if it does not have K5 and K2, 2,2 as minors, which implies the characterization of 3-realizable graphs of Belk and Connelly. Expand

Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion

- Mathematics, Computer Science
- Math. Program.
- 2021

By dualizing the clique tree conversion, the coupling due to the overlap constraints is guaranteed to be sparse over dense blocks, with a block sparsity pattern that coincides with the adjacency matrix of a tree. Expand

Combinatorial Conditions for the Unique Completability of Low-Rank Matrices

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2014

This work considers the problems of completing a low-rank positive semidefinite square matrix or aLow-rank rectangular matrix from a given subset of their entries, and studies the local and global uniqueness of such completions by analyzing the structure of the graphs determined by the positions of the known entries. Expand

Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs

- Mathematics, Computer Science
- Math. Program.
- 2020

This work studies a class of quadratically constrained quadratic programs (QCQPs), called diagonal QCQPs, and provides a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact, the first result establishing the exactness of the semideFinite relaxation for random general QCZPs. Expand

Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 2014

We study a new geometric graph parameter egd(G), defined as the smallest integer r>=1 for which any partial symmetric matrix, which is completable to a correlation matrix and whose entries are… Expand

#### References

SHOWING 1-10 OF 51 REFERENCES

Polynomial Instances of the Positive Semidefinite and Euclidean Distance Matrix Completion Problems

- Mathematics, Computer Science
- SIAM J. Matrix Anal. Appl.
- 2001

The matrix completion problem can be solved in polynomial time in the real number model for the class of graphs containing no homeomorph K4 and the completion problem is polynomially solvable for a class of graph including wheels of fixed length. Expand

Variants on the minimum rank problem: A survey II

- Mathematics
- 2011

The minimum rank problem for a (simple) graph $G$ is to determine the smallest possible rank over all real symmetric matrices whose $ij$th entry (for $i\neq j$) is nonzero whenever $\{i,j\}$ is an… Expand

The Gram Dimension of a Graph

- Mathematics, Philosophy
- ISCO
- 2012

It is shown that a graph has Gram dimension at most 4 if and only if it does not have K5 and K2, 2,2 as minors, which implies the characterization of 3-realizable graphs of Belk and Connelly. Expand

Complexity of the positive semidefinite matrix completion problem with a rank constraint

- Mathematics
- 2012

We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive semidefinite matrix of rank at most k. We show that… Expand

Embedded in the Shadow of the Separator

- Mathematics, Computer Science
- SIAM J. Optim.
- 2008

This work proves that, for any separator in the graph, at least one of the two separated node sets is embedded in the shadow (with the origin being the light source) of the convex hull of the separator. Expand

The rotational dimension of a graph

- Mathematics, Computer Science
- J. Graph Theory
- 2011

The rotational dimension of G is defined to be the minimal dimension k so that for all choices of lengths and weights an optimal solution can be found in ℝk and it is shown that this is a minor monotone graph parameter. Expand

The real positive semidefinite completion problem for series-parallel graphs

- Mathematics
- 1994

Abstract We consider the partial real symmetric matrices X whose diagonal entries are equal to 1 and whose off-diagonal entries are specified only on a subset of the positions. The question is to… Expand

Positive definite completions of partial Hermitian matrices

- Mathematics
- 1984

Abstract The question of which partial Hermitian matrices (some entries specified, some free) may be completed to positive definite matrices is addressed. It is shown that if the diagonal entries are… Expand

Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT

- Mathematics, Computer Science
- APPROX-RANDOM
- 2005

An improved rounding procedure for SDP solutions that lie in ℝ3 with a performance ratio of about 0.8818 is presented, which resolves an open problem posed by Feige and Schechtman [STOC'01]. Expand

A Remark on the Rank of Positive Semidefinite Matrices Subject to Affine Constraints

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2001

A short geometric proof of this result is given, which is used to improve a bound on realizability of weighted graphs as graphs of distances between points in Euclidean space, and its relation to theorems of Bohnenblust, Friedland and Loewy, and Au-Yeung and Poon. Expand