论文标题
稀疏0-1矩阵的最大决定因素和永久性
Maximum determinant and permanent of sparse 0-1 matrices
论文作者
论文摘要
我们证明，$ n \ times n $矩阵的最大决定因素，其中$ \ {0,1 \} $的条目和最多$ n+k $ non-Zero条目最多是$ 2^{k/3} $，当$ k $的最高$ 2^{k/3} $时，当$ k $的最佳可能是$ k $的3次。我们还基于边缘的数量，在$ C_4 $ free双方图中获得了一个完美匹配的次数，在稀疏的情况下，这会改善经典的布雷格曼对永久性的不平等。这种结合是紧密的，因为平等是通过6 vertex循环的顶点脱节联合形成的图表实现的。
We prove that the maximum determinant of an $n \times n $ matrix, with entries in $\{0,1\}$ and at most $n+k$ non-zero entries, is at most $2^{k/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 $C_4$-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.
