## Abstract

In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal I_{A} 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 I_{A} 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 A_{3 × 3} and A_{3 × 4}, defining the 3×3 and 3×4 transportation problems, we have u (A_{3 × 3}) = g (A_{3 × 3}) = 9 and u (A_{3 × 4}) = g (A_{3 × 4}) ≥ 27. Moreover, we prove that u (A_{a, b}) = g (A_{a, b}) = 2 (a + b) / gcd (a, b) for positive integers a, b and A_{a, b} = ((1, 1, 1, 1; 0, a, b, a + b)).

Original language | English |
---|---|

Pages (from-to) | 1558-1563 |

Number of pages | 6 |

Journal | Journal of Pure and Applied Algebra |

Volume | 213 |

Issue number | 8 |

DOIs | |

State | Published - Aug 2009 |

Externally published | Yes |