Markov bases of binary graph models of K_4-minor free graphs

摘要

The Markov width of a graph is a graph invariant defined as the maximum degree of a Markov basis element for the corresponding graph model for binary contingency tables. We show that a graph has Markov width at most four if and only if it contains no K_4 as a minor, answering a question of Develin and Sullivant. We also present a lower bound of order Ω(n~(2-ε)) on the Markov width of K_n.