Bounded Markov complexity for independent subsets

Let Δ\Delta be a simplicial complex on vertices {1,,n}\{1,\ldots,n\}, let its underlying graph be the graph whose edges are the two-element faces of Δ\Delta, and let MΔ,d\mathcal{M}_{\Delta,d} denote the universal Markov basis for the hierarchical model associated with Δ\Delta and level vector d=(d1,,dn)d=(d_1,\ldots,d_n). Suppose that {1,2,,j}\{1,2,\ldots,j\} is an independent subset of the underlying graph of Δ\Delta. For fixed dj+1,,dnd_{j+1},\ldots,d_n, there exist numbers (m1,,mj)=m(Δ;dj+1,,dn)(m_1,\ldots,m_j)=m(\Delta;d_{j+1},\ldots,d_n) such that every element in MΔ,d\mathcal{M}_{\Delta,d} has format smaller than

m1××mj×dj+1××dn.m_1\times\cdots\times m_j\times d_{j+1}\times\cdots\times d_n.

Bounded Markov complexity conjecture. If {1,2,,j}\{1,2,\ldots,j\} is an independent subset of the underlying graph of Δ\Delta, then the preceding bounded-format conclusion holds. This would generalize the established result for reducible simplicial complexes when the varying levels correspond to nonadjacent vertices. The conjecture asserts that independence alone is sufficient for bounded Markov complexity as the levels vary.

Sources & referencesView supporting material

Primary source

Serkan Hosten and Seth Sullivant, “A finiteness theorem for Markov bases of hierarchical models”, arXiv:math/0401379 (2008).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.