Maximal determinants of combinatorial matrices

Abstract

We prove that $\det A\le 6^{\frac{n}{6}}$ whenever $A\in \{0,1{\}}^{n\times n}$ contains at most $2n$ ones. We also prove an upper bound on the determinant of matrices with the $k$-consecutive ones property, a generalisation of the consecutive ones property, where each row is allowed to have up to $k$ blocks of ones. Finally, we prove an upper bound on the determinant of a path-edge incidence matrix in a tree and use that to bound the leaf rank of a graph in terms of its order.

17 pages