Journal of Combinatorics

Volume 3 (2012)

Number 4

A lower bound for the Graver complexity of the incidence matrix of a complete bipartite graph

Pages: 695 – 708

DOI: https://dx.doi.org/10.4310/JOC.2012.v3.n4.a7

Authors

Taisei Kudo (Graduate School of Information Science and Technology, The University of Tokyo, Japan)

Akimichi Takemura (Graduate School of Information Science and Technology, The University of Tokyo, Japan)

Abstract

We give an exponential lower bound for the Graver complexity of the incidence matrix of a complete bipartite graph of arbitrary size. Our result is a generalization of the result by Berstein and Onn for the complete bipartite graph $K_{3,r}$, $r≥3$.

Keywords

algebraic statistics, contingency table, threeway transportation program

Full Text (PDF format)

Published 21 February 2013