<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue4" %>
Markov Bases of Binary Graph Models
Mike Develin1 and Seth Sullivant2
1American Institute of Mathematics, 360 Portage Ave., Palo Alto, CA 94306-2244, USA
2Department of Mathematics, University of California-Berkeley, Berkeley, CA 94720-3840, USA
Annals of Combinatorics 7 (4) p.441-466 December, 2003
AMS Subject Classification: 05C99, 13P10, 62Q05
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.
Keywords: Markov bases, contingency tables, graphical models, hierarchical models, toric ideals


1. T. Christof, PORTA: a polyhedron representation transformation algorithm, version 1.3.1, available at ftp://elib.zib.de/pub/mathprog/polyth/index.html.

2. P. Diaconis and B. Sturmfels, Algebraic algorithms for sampling from conditional distributions, Ann. Statist. 26 (1998) 363每397.

3. A. Dobra, Markov bases for decomposable graphical models, Bernoulli 9 (6) (2003) 1每16.

4. A. Dobra and S. Sullivant, A divide-and-conquer algorithm for generating Markov bases of multi-way tables, Comput. Statist., to appear.

5. M. Dyer, L.A. Goldberg, C. Greenhill, M. Jerrum, and M. Mitzenmacher, An extension of path coupling and its application to the Glauber dynamics for graph colorings, SIAM J. Comput. 30 (2001) 1962每1975.

6. D. Geiger, C. Meek, and B. Sturmfels, On the toric algebra of graphical models, manuscript, 2002.

7. D. Grayson and M. Stillman, Macaulay 2: a software system for research in algebraic geometry, available at http://www.math.uiuc.edu/Macaulay2/.

8. R. Hemmecke, 4ti2: computation of Hilbert bases, Graver bases, toric Gröbner bases and more, available at http://www.4ti2.de/.

9. S. Hosten and S. Sullivant, Gröbner bases and polyhedral geometry of cyclic and reducible models, J. Combin. Theory, Ser. A 100 (2) (2002) 277每301.

10. S. Lauritzen, Graphical Models, Oxford University Press, New York, 1996.

11. C. Poupard, Deux propriÉtés des arbres binaires ordonnés stricts, Europ. J. Combin. 10 (1989) 369每374.

12. R. Read and R. Wilson, An Atlas of Graphs, Oxford University Press, New York, 1999.

13. B. Sturmfels, Grébner Bases and Convex Polytopes, University Lecture Series Vol. 8, Amer. Math. Soc., Providence, 1995.

14. B. Sturmfels, Solving Systems of Polynomial Equations, CBMS Regional Conference Series in Mathematics, Vol. 97, Amer. Math. Soc., Providence, 2002.

15. A. Takken, Monte Carlo goodness-of-fit tests for discrete data, Ph.D. Thesis, Stanford University, 1999.

16. E. Vigoda. Improved bounds for sampling colorings, J. Math. Phys. 41 (3) (2000) 1555每 1569.

17. J.S. Wang, R.H. Swendsen, and R. Kotecký, Antiferromagnetic Potts models, Phys. Rev. Lett. 63 (2) (1989) 109每112.