Markov bases of binary graph models of K₄-minor free graphs

2008/10/10 by Daniel Král', Daniel Král͏̌, Serguei Norine +5
Computer Science · Mathematics · #05C99 (Primary) #05E99 (Secondary) #62H17 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #math.CO #msc:05C99 #msc:05E99 #msc:62H17

paper · pdf · doi:10.48550/arxiv.0810.1979

arxiv created 2008/10/10 · openalex publication_date 2008/10/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Abstract

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₄ 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.

Related

• Markov bases of binary graph models
• The Markov basis of K_3,N
• Structural perspective on constraint-based learning of Markov networks
• Markov bases and subbases for bounded contingency tables
• Information-theoretic limits of selecting binary graphical models in high dimensions