On the Gröbner complexity of matrices |
| |
Authors: | Raymond Hemmecke Kristen A Nairn |
| |
Institution: | a University of Magdeburg, Germany b College of St. Benedict, MN, USA |
| |
Abstract: | In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal IA coincides with the Graver basis of A, then the Gröbner complexity u(A) and the Graver complexity g(A) of its higher Lawrence liftings agree, too. In fact, if the universal Gröbner basis of IA coincides with the Graver basis of A, then also the more general complexities u(A,B) and g(A,B) agree for arbitrary B. We conclude that for the matrices A3×3 and A3×4, defining the 3×3 and 3×4 transportation problems, we have u(A3×3)=g(A3×3)=9 and u(A3×4)=g(A3×4)≥27. Moreover, we prove that u(Aa,b)=g(Aa,b)=2(a+b)/gcd(a,b) for positive integers a,b and . |
| |
Keywords: | 13P10 90C10 |
本文献已被 ScienceDirect 等数据库收录! |
|