Abstract: In this paper we show that if for an integer matrix A the universal Gr"obner basis of the associated toric ideal Ideal_A coincides with the Graver basis of A, then the Gr"obner complexity u(A) and the Graver complexity g(A) of its higher Lawrence liftings agree, too. We conclude that for the matrices A_{3 imes 3} and A_{3 imes 4}, defining the 3 imes 3 and 3 imes 4 transportation problems, we have u(A_{3 imes 3})=g(A_{3 imes 3})=9 and u(A_{3 imes 4})=g(A_{3 imes 4})geq 27. Moreover, we prove u(A_{a,b})=g(A_{a,b})=2(a+b)/gcd(a,b) for positive integers a,b and A_{a,b}=(�egin{smallmatrix} 1 & 1 & 1 & 1 0 & a & b & a+b end{smallmatrix}).
The author show that if for an integer matrix \(A\) the universal Gröbner basis of the associated toric ideal IA coincides with the Graver bases of \(A\), then the Gröbner complexity and Graver complexity of its higher Lawrence liftings agree, too. In Section 2, they prove their main result of this paper.
Recommendations
Cites work
- A finiteness theorem for Markov bases of hierarchical models
- Higher Lawrence configurations.
- Lexicographic Gröbner bases for transportation problems of format \(r\times 3\times 3\)
- Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
- On the foundations of linear and integer linear programming I
- On the positive sums property and the computation of Graver test sets
- Variation of cost functions in integer programming
Cited in
(14)- Vandermonde matrices, NP-completeness and transversal subspaces
- Identifying complexity by means of matrices
- Lower bounds on the graver complexity of M-fold matrices
- On the fraction of matrices with maximal additive complexity
- On the complexity of the ℰ2 Grzegorczyk class
- Standard pairs for lawrence-type matrices and their applications to several lawrence-type integer programs
- Universal Gröbner bases of colored partition identities
- Asymptotic behavior of Markov complexity
- The Graver complexity of integer programming
- Graver bases of shifted numerical semigroups with 3 generators
- On the Graver complexity of codimension \(2\) matrices
- Generalized robust toric ideals
- Markov bases and generalized Lawrence liftings
- Complexity measures of sign matrices
This page was built for publication: On the Gröbner complexity of matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017673)
