(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 maximumdegree of a Markov basis element for the corresponding graph model for binary contingencytables. We describe a degree four Markov basis for the model when the underlying graph is a cycleand generalize this result to the complete bipartite graph K2,n. We also give a combinatorialclassification of degree two and three Markov basis moves as well as a Buchberger-free algorithmto compute moves of arbitrary given degree. Finally, we compute the algebraic degree ofthe model when the underlying graph is a forest.AMS Subject Classification: 05C99, 13P10, 62Q05.
