Graphs with sparsity order at most two: the complex case

DOI10.1080/03081087.2016.1274362zbMATH Open1381.05060arXiv1804.08931OpenAlexW2568259186MaRDI QIDQ4603775FDOQ4603775

E. M. Klem, Sanne ter Horst

Publication date: 19 February 2018

Published in: Linear and Multilinear Algebra (Search for Journal in Brave)

Abstract: The sparsity order of a (simple undirected) graph is the highest possible rank (over $mathbbR$ or $mathbbC$) of the extremal elements in the matrix cone that consists of positive semidefinite matrices with prescribed zeros on the positions that correspond to non-edges of the graph (excluding the diagonal entries). The graphs of sparsity order 1 (for both $mathbbR$ and $mathbbC$) correspond to chordal graphs, those graphs that do not contain a cycle of length greater than three, as an induced subgraph, or equivalently, is a clique-sum of cliques. There exist analogues, though more complicated, characterizations of the case where the sparsity order is at most 2, which are different for $mathbbR$ and $mathbbC$. The existing proof for the complex case, is based on the result for the real case. In this paper we provide a more elementary proof of the characterization of the graphs whose complex sparsity order is at most two. Part of our proof relies on a characterization of the $P_4,overline{K}_3$-free graphs, with $P_4$ the path of length 3 and $overline{K}_3$ the stable set of cardinality 3, and of the class of clique-sums of such graphs.

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

Recommendations

• On the sparsity order of a graph and its deficiency in chordality
• scientific article
• Positive semidefinite matrices with a given sparsity pattern
• Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors
• Sparse matrix decompositions and graph characterizations

zbMATH Keywords

forbidden subgraphssparsity ordermatrix cones

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hermitian, skew-Hermitian, and related matrices (15B57) Structural characterization of families of graphs (05C75) Convex sets and cones of operators (47L07)

Cites Work

• Graph Classes: A Survey
• Title not available (Why is that?)
• On Majorization, Factorization, and Range Inclusion of Operators on Hilbert Space
• On rigid circuit graphs
• Clique partitions of the cocktail party graph
• Positive definite completions of partial Hermitian matrices
• Positive semidefinite matrices with a given sparsity pattern
• On the sparsity order of a graph and its deficiency in chordality
• The Ranks of Extremal Positive Semidefinite Matrices with Given Sparsity Pattern
• A non-existence result on cyclic cycle-decompositions of the cocktail party graph
• Dihedral Hamiltonian Cycle Systems of the Cocktail Party Graph
• Axiomatic Characterization of the Median and Antimedian Functions on Cocktail-Party Graphs and Complete Graphs
• Title not available (Why is that?)

Cited In (2)

• Title not available (Why is that?)
• On the sparsity order of a graph and its deficiency in chordality

This page was built for publication: Graphs with sparsity order at most two: the complex case

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