[{"publication_status":"published","abstract":[{"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.","lang":"eng"}],"title":"Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without K5 minors","status":"public","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.","intvolume":" 509","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:49:40Z","_id":"1293","date_published":"2016-11-15T00:00:00Z","publication":"Linear Algebra and Its Applications","citation":{"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.","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","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","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.","short":"L.T. Solus, C. Uhler, R. Yoshida, Linear Algebra and Its Applications 509 (2016) 247–275.","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."},"type":"journal_article","language":[{"iso":"eng"}],"scopus_import":1,"page":"247 - 275","project":[{"_id":"2530CA10-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Gaussian Graphical Models: Theory and Applications","grant_number":"Y 903-N35"}],"author":[{"first_name":"Liam T","id":"2AADA620-F248-11E8-B48F-1D18A9856A87","full_name":"Solus, Liam T","last_name":"Solus"},{"id":"49ADD78E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7008-0216","full_name":"Uhler, Caroline","last_name":"Uhler","first_name":"Caroline"},{"first_name":"Ruriko","last_name":"Yoshida","full_name":"Yoshida, Ruriko"}],"volume":509,"department":[{"_id":"CaUh"}],"publist_id":"6024","month":"11","doi":"10.1016/j.laa.2016.07.026","date_created":"2018-12-11T11:51:11Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/pdf/1506.06702.pdf"}],"oa_version":"Preprint","oa":1,"year":"2016","quality_controlled":"1","publisher":"Elsevier","day":"15"},{"intvolume":" 20","date_created":"2018-12-11T11:50:27Z","publist_id":"6202","month":"12","doi":"10.1007/s00026-016-0325-x","volume":20,"status":"public","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.","issue":"4","publication_status":"published","author":[{"full_name":"Hibi, Takayugi","last_name":"Hibi","first_name":"Takayugi"},{"last_name":"Solus","full_name":"Liam Solus","id":"2AADA620-F248-11E8-B48F-1D18A9856A87","first_name":"Liam T"}],"abstract":[{"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.","lang":"eng"}],"extern":1,"title":"Facets of the r-stable (n, k)-hypersimplex","publisher":"Springer","day":"01","page":"815 - 829","tmp":{"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)","image":"/images/cc_by.png"},"citation":{"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.","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","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","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.","short":"T. Hibi, L.T. Solus, Annals of Combinatorics 20 (2016) 815–829.","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."},"quality_controlled":0,"type":"journal_article","_id":"1156","date_published":"2016-12-01T00:00:00Z","year":"2016","publication":"Annals of Combinatorics","date_updated":"2021-01-12T06:48:43Z"}]