{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:25:49Z","timestamp":1787325949596,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>In 2010, M. Studen\u00fd, R. Hemmecke, and S. Lindner explored a new algebraic description of graphical models, called characteristic imsets. Compared with standard imsets, characteristic imsets have several advantages: they are still unique vector representatives of conditional independence structures, 0-1 vectors, and more intuitive in terms of graphs than standard imsets. After defining a characteristic imset polytope (cim-polytope) as the convex hull of all characteristic imsets with a given set of nodes, they also showed that a model selection in graphical models, which maximizes a quality criterion, can be converted into a linear programming problem over the cim-polytope. However, in general, for a fixed set of nodes, the cim-polytope can have exponentially many vertices over an exponentially high dimension. Therefore, in this paper, we focus on the family of directed acyclic graphs whose nodes have a fixed order. This family includes diagnosis models described by bipartite graphs with a set of $m$ nodes and a set of $n$ nodes for any $m, n \\in \\mathbb{Z}_+$. We first consider cim-polytopes for all diagnosis models and show that these polytopes are direct products of simplices. Then we give a combinatorial description of all edges and all facets of these polytopes. Finally, we generalize these results to the cim-polytopes for all Bayesian networks with a fixed underlying ordering of nodes with or without fixed (or forbidden) edges.<\/jats:p>","DOI":"10.1137\/130933848","type":"journal-article","created":{"date-parts":[[2015,4,2]],"date-time":"2015-04-02T13:56:21Z","timestamp":1427982981000},"page":"697-715","source":"Crossref","is-referenced-by-count":2,"title":["The Characteristic Imset Polytope of Bayesian Networks with Ordered Nodes"],"prefix":"10.1137","volume":"29","author":[{"given":"Jing","family":"Xi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruriko","family":"Yoshida","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,4,2]]},"reference":[{"key":"atypb1","unstructured":"H. Akaike,\n                      Information theory and an extension of the maximum likelihood principle\n                      , in Proceedings of the Second International Symposium on Information Theory, B. Petrox and F. Caski, eds., 1973, pp. 267-281."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1031833662"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF00994110"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1089\/106652700750050961"},{"key":"atypb5","first-page":"12","author":"Jiang X.","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1999.0328"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"S. L. Lauritzen,\n                      Graphical Models\n                      , Clarendon Press, Oxford, UK, 1996.","DOI":"10.1093\/oso\/9780198522195.001.0001"},{"key":"atypb8","unstructured":"S. Lindner,\n                      Discrete Optimisation in Machine Learning: Learning of Bayesian Network Structures and Conditional Independence Implication\n                      , Ph.D. thesis, Technische Universita\u0308t Mu\u0308nchen, 2012."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/S0888-613X(01)00036-6"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176344136"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1055\/s-0038-1634846"},{"key":"atypb12","unstructured":"M. Studeny\u0301,\n                      Probabilistic Conditional Independence Structures\n                      , Springer, New York, 2005."},{"key":"atypb13","unstructured":"M. Studeny\u0301, R. Hemmecke, and S. Lindner,\n                      Characteristic imset: A simple algebraic representative of a Bayesian network structure\n                      , in Proceedings of the 5th European Workshop on Probabilistic Graphical Models, 2010, pp. 257-264."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2010.01.014"},{"key":"atypb15","unstructured":"J. Uebersax,\n                      Genetic Counseling and Cancer Risk Modeling: An Application of Bayes Nets,\n                      Ravenpack International, Marbella, Spain, 2004."},{"key":"atypb16","first-page":"204","author":"Vomlel J.","year":"2012","journal-title":"Proceedings of WUPES"},{"key":"atypb17","unstructured":"J. Xi,\n                      Polytopes Arising from Binary Multi-way Contingency Tables and Characteristic Imsets for Bayesian Networks\n                      , Ph.D. thesis, University of Kentucky, Lexington, 2013."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"G. Ziegler,\n                      Lectures on Polytopes\n                      , Springer, New York, 1994.","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130933848","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:24:45Z","timestamp":1787322285000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130933848"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130933848"],"URL":"https:\/\/doi.org\/10.1137\/130933848","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}