Lower bounds on the graver complexity of \(M\)-fold matrices (Q259721): Difference between revisions

The Graver basis of a \(d\times n\) integer matrix \(A\) is a finite set of integer \(n\)-vectors in \(\mathrm{ker}(A)\) that allows the representation of any integer \(n\)-vector in \(\mathrm{ker}(A)\) as a nonnegative sign-compatible integer linear combination. A zero-valued integer linear combination on \(k\) nonzero integer vectors is called primitive if all its coefficients are nonzero and relatively prime and no \(k-1\) of the \(k\) vectors satisfy a nontrivial linear relation. It is well known that that there can only be one primitive relation on a given set of vectors. As their main result, the authors present a construction that turns certain primitive relations on Graver basis elements of an \(M\)-fold matrix \(A^{(M)}\) into primitive relations on Graver basis elements of \(A^{(M+1)}\). Applying this construction to the \(M\)-fold matrix \(A_{(3\times M)}\) yields a stronger lower bound on the Graver complexity of \(A_{(3\times M)}\) for \(M\geq 4\) than the one obtained by \textit{Y. Berstein} and \textit{S. Onn} [Ann. Comb. 13, No. 3, 289--296 (2009; Zbl 1231.90295)], and also gives a lower bound on the Graver complexity of general \(M\)-fold matrices \(A^{(M)}\). Finally, they show that the new lower bound on the Graver complexity of \(A_{(3\times M)}\) mentioned above is still not tight.