---
_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. *Linear Algebra and Its
Applications*. 2016;509:247-275. doi:10.1016/j.laa.2016.07.026
apa: Solus, L. T., Uhler, C., & Yoshida, R. (2016). Extremal positive semidefinite
matrices whose sparsity pattern is given by graphs without K5 minors. *Linear
Algebra and Its Applications*. Elsevier. https://doi.org/10.1016/j.laa.2016.07.026
chicago: Solus, Liam T, Caroline Uhler, and Ruriko Yoshida. “Extremal Positive Semidefinite
Matrices Whose Sparsity Pattern Is given by Graphs without K5 Minors.” *Linear
Algebra and Its Applications*. Elsevier, 2016. https://doi.org/10.1016/j.laa.2016.07.026.
ieee: L. T. Solus, C. Uhler, and R. Yoshida, “Extremal positive semidefinite matrices
whose sparsity pattern is given by graphs without K5 minors,” *Linear Algebra
and Its Applications*, 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.” *Linear Algebra and Its Applications*,
vol. 509, Elsevier, 2016, pp. 247–75, doi:10.1016/j.laa.2016.07.026.
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'
...
---
_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. *Annals of
Combinatorics*. 2016;20(4):815-829. doi:10.1007/s00026-016-0325-x
apa: Hibi, T., & Solus, L. T. (2016). Facets of the r-stable (n, k)-hypersimplex.
*Annals of Combinatorics*. Springer. https://doi.org/10.1007/s00026-016-0325-x
chicago: Hibi, Takayugi, and Liam T Solus. “Facets of the R-Stable (n, k)-Hypersimplex.”
*Annals of Combinatorics*. Springer, 2016. https://doi.org/10.1007/s00026-016-0325-x.
ieee: T. Hibi and L. T. Solus, “Facets of the r-stable (n, k)-hypersimplex,” *Annals
of Combinatorics*, 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.”
*Annals of Combinatorics*, vol. 20, no. 4, Springer, 2016, pp. 815–29, doi:10.1007/s00026-016-0325-x.
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'
...