Markov Bases of Binary Graph Models |
| |
Authors: | Email author" target="_blank">Mike?DevelinEmail author Seth?Sullivant |
| |
Institution: | (1) American Institute of Mathematics, 360 Portage Ave., 94306-2244 Palo Alto, CA, USA;(2) Department of Mathematics, University of California-Berkeley, 94720-3840 Berkeley, CA, USA |
| |
Abstract: | This paper is concerned with the topological invariant of a graph given by the maximum
degree of a Markov basis element for the corresponding graph model for binary contingency
tables. We describe a degree four Markov basis for the model when the underlying graph is a cycle
and generalize this result to the complete bipartite graph
K2,n. We also give a combinatorial
classification of degree two and three Markov basis moves as well as a Buchberger-free algorithm
to compute moves of arbitrary given degree. Finally, we compute the algebraic degree of
the model when the underlying graph is a forest.AMS Subject Classification: 05C99, 13P10, 62Q05. |
| |
Keywords: | Markov bases contingency tables graphical models hierarchical models toric ideals |
本文献已被 SpringerLink 等数据库收录! |
|