Maximum determinant and permanent of sparse 0-1 matrices (Q2132515)

This paper considers the maximum determinant of an \(n \times n\) matrix, with entries in \(\{0,1\}\). Many upper bounds on determinants have been given in the literature, in particular for matrices with all entries \(0\) or \(1\). For example, the classical Hadamard inequality together with arithmetic and geometric mean inequalities imply \[ \det(A) \leq \prod_{i=1}^n \left( \sum_{i=1}^n a_{i,j}^2 \right) \leq 2^{n/2} \,. \] This bound was improved by \textit{H. J. Ryser} [Can. J. Math. 8, 245--249 (1956; Zbl 0071.35903)], but still these bounds are not the best possible for sparse matrices. \textit{H. Bruhn} and \textit{D. Rautenbach} [Linear Algebra Appl. 553, 37--57 (2018; Zbl 1393.15025)] proved that if \(A \in \{0,1\}^{n \times n}\) has at most \(2n\) non-zero entries, then \[ |\det(A)| \leq 2^{n/6} \cdot 3^{n/6}. \] They also conjectured that the determinant of \(A\) is at most \(2^{n/3}\) in this case. The main result of the paper solves this conjecture. It is proved that if \(A \in \{0,1\}^{n \times n}\) has at most \(n+k\) non-zero entries, then \[ |\det(A)| \leq 2^{k/3}. \] The authors also obtain an upper bound on the number of perfect matchings in \(C_4\)-free bipartite graphs based on the number of edges, which, in the sparse case, improves the classical Bregman inequality for permanents. Finally, they offer three conjectures which may be studied in the future.