Lower Bounds on the Graver Complexity of M-Fold Matrices

In this paper, we present a construction that turns certain relations on Graver basis elements of an M-fold matrix (Formula presented.) into relations on Graver basis elements of an (Formula presented.) -fold matrix (Formula presented.). In doing so, we strengthen the bound on the Graver complexity of the M-fold matrix (Formula presented.) from (Formula presented.) (Berstein and Onn) to (Formula presented.) , for (Formula presented.). Moreover, we give a lower bound on the Graver complexity (Formula presented.) of general (Formula presented.) -fold matrices (Formula presented.) and we prove that the bound for (Formula presented.) is not tight.