Markov bases of binary graph models

2003/08/28 by Mike Develin, Develin, Mike, Seth Sullivant +1
Mathematics · #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics #Statistics Theory (math.ST) #math.AC #math.CO #math.ST #stat.TH

paper · pdf · doi:10.48550/arxiv.math/0308280

24 pages, 1 figure

arxiv created 2003/08/28 · arxiv updated 2009/12/01

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.

Related

• Markov bases of binary graph models of K₄-minor free graphs
• The Markov basis of K_3,N
• Markov degree of configurations defined by fibers of a configuration
• Degree Bounds for a Minimal Markov Basis for the Three-State Toric Homogeneous Markov Chain Model
• Markov bases and subbases for bounded contingency tables