Markov Bases of Binary Graph Models

Mike Develin^{1} and Seth Sullivant^{2}

develin@post.harvard.edu

seths@math.berkeley.edu

Annals of Combinatorics 7 (4) p.441-466 December, 2003

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 *K*_{2, 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.

References:

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.