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

DOI10.4310/JOC.2012.V3.N4.A7MaRDI QIDQ2375856zbMATH OpenFDO

Authors Taisei Kudo, Akimichi Takemura

Publication date 25 June 2013

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.4674

zbMATH Keywords

algebraic statisticscontingency tablethree-way transportation program

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Integer programming (90C10)

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 (2009) for 3xr complete bipartite graphs, r ge 3.

Recommendations

• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• On the complexity of construction of complete and complete bipartite graphs
• Lower bounds on the graver complexity of M-fold matrices
• An improved lower bound for the degree Kirchhoff index of bipartite graphs
• On lower bounds for numbered complete graphs
• Lower bounds for combinatorial problems on graphs
• The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
• Lower bounds for the energy of (bipartite) graphs
• On a lower bound for the connectivity of the independence complex of a graph
• Remarks on the Graovac-Ghorbani index of bipartite graphs

Cited in

(8)

• Unboundedness of Markov complexity of monomial curves in \(\mathbb{A}^n\) for \(n \geq 4\)
• Convex integer optimization by constantly many linear counterparts
• Lower bounds on the graver complexity of M-fold matrices
• Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
• Asymptotic behavior of Markov complexity
• The Graver complexity of integer programming
• Does subset sum admit short proofs?
• On the Graver complexity of codimension \(2\) matrices

This page was built for publication: A lower bound for the Graver complexity of the incidence matrix of a complete bipartite graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2375856)