---
_id: '1156'
abstract:
- lang: eng
  text: Let k, n, and r be positive integers with k < n and r≤⌊nk⌋. We determine
    the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the
    r-stable n, k-hypersimplex has exactly 2n facets for every r<⌊nk⌋. We then
    utilize the equations of the facets to study when the r-stable hypersimplex is
    Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein
    r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices
    known to have unimodal Ehrhart δ-vectors.
acknowledgement: "Liam Solus was supported by a 2014 National Science Foundation/Japan
  Society for the Promotion of Science East Asia and Pacific Summer Institute Fellowship.
  \nOpen access funding provided by IST Austria."
author:
- first_name: Takayugi
  full_name: Hibi, Takayugi
  last_name: Hibi
- first_name: Liam T
  full_name: Liam Solus
  id: 2AADA620-F248-11E8-B48F-1D18A9856A87
  last_name: Solus
citation:
  ama: Hibi T, Solus LT. Facets of the r-stable (n, k)-hypersimplex. <i>Annals of
    Combinatorics</i>. 2016;20(4):815-829. doi:<a href="https://doi.org/10.1007/s00026-016-0325-x">10.1007/s00026-016-0325-x</a>
  apa: Hibi, T., &#38; Solus, L. T. (2016). Facets of the r-stable (n, k)-hypersimplex.
    <i>Annals of Combinatorics</i>. Springer. <a href="https://doi.org/10.1007/s00026-016-0325-x">https://doi.org/10.1007/s00026-016-0325-x</a>
  chicago: Hibi, Takayugi, and Liam T Solus. “Facets of the R-Stable (n, k)-Hypersimplex.”
    <i>Annals of Combinatorics</i>. Springer, 2016. <a href="https://doi.org/10.1007/s00026-016-0325-x">https://doi.org/10.1007/s00026-016-0325-x</a>.
  ieee: T. Hibi and L. T. Solus, “Facets of the r-stable (n, k)-hypersimplex,” <i>Annals
    of Combinatorics</i>, vol. 20, no. 4. Springer, pp. 815–829, 2016.
  ista: Hibi T, Solus LT. 2016. Facets of the r-stable (n, k)-hypersimplex. Annals
    of Combinatorics. 20(4), 815–829.
  mla: Hibi, Takayugi, and Liam T. Solus. “Facets of the R-Stable (n, k)-Hypersimplex.”
    <i>Annals of Combinatorics</i>, vol. 20, no. 4, Springer, 2016, pp. 815–29, doi:<a
    href="https://doi.org/10.1007/s00026-016-0325-x">10.1007/s00026-016-0325-x</a>.
  short: T. Hibi, L.T. Solus, Annals of Combinatorics 20 (2016) 815–829.
date_created: 2018-12-11T11:50:27Z
date_published: 2016-12-01T00:00:00Z
date_updated: 2021-01-12T06:48:43Z
day: '01'
doi: 10.1007/s00026-016-0325-x
extern: 1
intvolume: '        20'
issue: '4'
month: '12'
page: 815 - 829
publication: Annals of Combinatorics
publication_status: published
publisher: Springer
publist_id: '6202'
quality_controlled: 0
status: public
title: Facets of the r-stable (n, k)-hypersimplex
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
volume: 20
year: '2016'
...
---
_id: '1293'
abstract:
- lang: eng
  text: For a graph G with p vertices the closed convex cone S⪰0(G) consists of all
    real positive semidefinite p×p matrices whose sparsity pattern is given by G,
    that is, those matrices with zeros in the off-diagonal entries corresponding to
    nonedges of G. The extremal rays of this cone and their associated ranks have
    applications to matrix completion problems, maximum likelihood estimation in Gaussian
    graphical models in statistics, and Gauss elimination for sparse matrices. While
    the maximum rank of an extremal ray in S⪰0(G), known as the sparsity order of
    G, has been characterized for different classes of graphs, we here study all possible
    extremal ranks of S⪰0(G). We investigate when the geometry of the (±1)-cut polytope
    of G yields a polyhedral characterization of the set of extremal ranks of S⪰0(G).
    For a graph G without K5 minors, we show that appropriately chosen normal vectors
    to the facets of the (±1)-cut polytope of G specify the off-diagonal entries of
    extremal matrices in S⪰0(G). We also prove that for appropriately chosen scalars
    the constant term of the linear equation of each facet-supporting hyperplane is
    the rank of its corresponding extremal matrix in S⪰0(G). Furthermore, we show
    that if G is series-parallel then this gives a complete characterization of all
    possible extremal ranks of S⪰0(G). Consequently, the sparsity order problem for
    series-parallel graphs can be solved in terms of polyhedral geometry.
acknowledgement: We wish to thank Alexander Engström and Bernd Sturmfels for various
  valuable discussions and insights. We also thank the two anonymous referees for
  their thoughtful feedback on the paper. CU was partially supported by the Austrian
  Science Fund (FWF) Y 903-N35.
author:
- first_name: Liam T
  full_name: Solus, Liam T
  id: 2AADA620-F248-11E8-B48F-1D18A9856A87
  last_name: Solus
- first_name: Caroline
  full_name: Uhler, Caroline
  id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
  last_name: Uhler
  orcid: 0000-0002-7008-0216
- first_name: Ruriko
  full_name: Yoshida, Ruriko
  last_name: Yoshida
citation:
  ama: Solus LT, Uhler C, Yoshida R. Extremal positive semidefinite matrices whose
    sparsity pattern is given by graphs without K5 minors. <i>Linear Algebra and Its
    Applications</i>. 2016;509:247-275. doi:<a href="https://doi.org/10.1016/j.laa.2016.07.026">10.1016/j.laa.2016.07.026</a>
  apa: Solus, L. T., Uhler, C., &#38; Yoshida, R. (2016). Extremal positive semidefinite
    matrices whose sparsity pattern is given by graphs without K5 minors. <i>Linear
    Algebra and Its Applications</i>. Elsevier. <a href="https://doi.org/10.1016/j.laa.2016.07.026">https://doi.org/10.1016/j.laa.2016.07.026</a>
  chicago: Solus, Liam T, Caroline Uhler, and Ruriko Yoshida. “Extremal Positive Semidefinite
    Matrices Whose Sparsity Pattern Is given by Graphs without K5 Minors.” <i>Linear
    Algebra and Its Applications</i>. Elsevier, 2016. <a href="https://doi.org/10.1016/j.laa.2016.07.026">https://doi.org/10.1016/j.laa.2016.07.026</a>.
  ieee: L. T. Solus, C. Uhler, and R. Yoshida, “Extremal positive semidefinite matrices
    whose sparsity pattern is given by graphs without K5 minors,” <i>Linear Algebra
    and Its Applications</i>, vol. 509. Elsevier, pp. 247–275, 2016.
  ista: Solus LT, Uhler C, Yoshida R. 2016. Extremal positive semidefinite matrices
    whose sparsity pattern is given by graphs without K5 minors. Linear Algebra and
    Its Applications. 509, 247–275.
  mla: Solus, Liam T., et al. “Extremal Positive Semidefinite Matrices Whose Sparsity
    Pattern Is given by Graphs without K5 Minors.” <i>Linear Algebra and Its Applications</i>,
    vol. 509, Elsevier, 2016, pp. 247–75, doi:<a href="https://doi.org/10.1016/j.laa.2016.07.026">10.1016/j.laa.2016.07.026</a>.
  short: L.T. Solus, C. Uhler, R. Yoshida, Linear Algebra and Its Applications 509
    (2016) 247–275.
date_created: 2018-12-11T11:51:11Z
date_published: 2016-11-15T00:00:00Z
date_updated: 2021-01-12T06:49:40Z
day: '15'
department:
- _id: CaUh
doi: 10.1016/j.laa.2016.07.026
intvolume: '       509'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/pdf/1506.06702.pdf
month: '11'
oa: 1
oa_version: Preprint
page: 247 - 275
project:
- _id: 2530CA10-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Y 903-N35
  name: 'Gaussian Graphical Models: Theory and Applications'
publication: Linear Algebra and Its Applications
publication_status: published
publisher: Elsevier
publist_id: '6024'
quality_controlled: '1'
scopus_import: 1
status: public
title: Extremal positive semidefinite matrices whose sparsity pattern is given by
  graphs without K5 minors
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 509
year: '2016'
...