Maximum determinant and permanent of sparse 0-1 matrices

Igor Araujo, József Balogh, Yuzhou Wang

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that the maximum determinant of an n×n matrix, with entries in {0,1} and at most n+k non-zero entries, is at most 2k/3, which is best possible when k is a multiple of 3. This result solves a conjecture of Bruhn and Rautenbach. We also obtain an upper bound on the number of perfect matchings in C4-free bipartite graphs based on the number of edges, which, in the sparse case, improves on the classical Bregman's inequality for permanents. This bound is tight, as equality is achieved by the graph formed by vertex disjoint union of 6-vertex cycles.

Original languageEnglish (US)
Pages (from-to)194-228
Number of pages35
JournalLinear Algebra and Its Applications
Volume645
DOIs
StatePublished - Jul 15 2022

Keywords

  • 0,1 matrices
  • Determinant
  • Permanent
  • Sparse matrices

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Maximum determinant and permanent of sparse 0-1 matrices'. Together they form a unique fingerprint.

Cite this