{
  "id": "1804.08931",
  "version": "v1",
  "published": "2018-04-24T09:48:45.000Z",
  "updated": "2018-04-24T09:48:45.000Z",
  "title": "Graphs with sparsity order at most two: The complex case",
  "authors": [
    "S. ter Horst",
    "E. M. Klem"
  ],
  "comment": "20 pages",
  "journal": "Linear and Multilinear Algebra 65 (2017), 2367-2386",
  "doi": "10.1080/03081087.2016.1274362",
  "categories": [
    "math.FA",
    "math.CO"
  ],
  "abstract": "The sparsity order of a (simple undirected) graph is the highest possible rank (over ${\\mathbb R}$ or ${\\mathbb C}$) 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 ${\\mathbb R}$ and ${\\mathbb C}$) 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 ${\\mathbb R}$ and ${\\mathbb C}$. 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-04-24T09:48:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75",
      "05C50",
      "47L07",
      "15B57"
    ],
    "keywords": [
      "complex case",
      "characterization",
      "complex sparsity order",
      "correspond",
      "diagonal entries"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Taylor-Francis"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}