Markov bases and generalized Lawrence liftings (Q891951)

Let \(A\) be an \(m \times n\) matrix with integer entries and let \(\mathcal{L}(A):=\text{Ker}_{\mathbb{Z}}(A)\) be the corresponding lattice of \(\mathbb{Z}^{n}\). A finite set of vectors \(M \subset \mathcal{L}(A)\) is called a Markov basis of \(A\) if for every \({\mathbf w}, {\mathbf u} \in \mathbb{N}^{n}\) such that \({\mathbf w}-{\mathbf u} \in \mathcal{L}(A)\), there exists a subset \(\{{\mathbf v}_{i}: i=1,\ldots,s\}\) of \(M\) such that \({\mathbf w}+\sum_{i=1}^{s}{\mathbf v}_{i}={\mathbf u}\) and for each \(p\) such that \(1 \leq p \leq s\), \({\mathbf w}+\sum_{i=1}^{p}{\mathbf v}_{i} \in \mathbb{N}^{n}\). A Markov basis \(M\) of \(A\) is minimal if no subset of \(M\) is a Markov basis of \(A\). Minimal Markov bases of \(A\) correspond to minimal binomial generating sets of the associated lattice ideal. In this paper, the authors provide necessary and sufficient conditions for the elements of a minimal Markov basis to be (a) inside the universal Gröbner basis and (b) inside the Graver basis. Furthermore, for \(r \geq 2\) and \(B\) an \(p \times n\) matrix with integer entries, they study minimal Markov bases of the generalized Lawrence lifting \(\Lambda(A,B,r)\). They prove that when the lattice \(\mathcal{L}(\Lambda(A,B,r))\) is positive, all minimal Markov bases of \(\Lambda(A,B,r)\) have the same complexity.