The theorem in question is due to \textit{L. M. Brégman} [Dokl. Akad. Nauk SSSR 211, 27-30 (1973; Zbl 0293.15010)]. It states that, if \(A\) is an \(n \times n\) \((0,1)\)-matrix whose row sums are \(r_{i}\) (\(i = 1,2,\ldots ,n\)), then \(\text{perm}(A) \leq \prod^{n}_{i=1} (r_{i}!)^{1/r_{i}}\). Several proofs are known. In the present paper the author presents a proof based on an entropy argument.
Recommendations
Cited in
(33)- A proof of the Beyer-Stein-Ulam relation between complexity and entropy
- Proof of an entropy conjecture of Leighton and Moitra
- A proof of the upper matching conjecture for large graphs
- Enumerating extensions of mutually orthogonal Latin squares
- New bounds for perfect \(k\)-hashing
- A proof of Tomescu's graph coloring conjecture
- An upper bound for permanents of nonnegative matrices
- On the maximum number of Latin transversals
- An Entropy-Based Proof for the Moore Bound for Irregular Graphs
- An upper bound on the number of Steiner triple systems
- Permanents of multidimensional matrices: properties and applications
- A proof of the estimation from below in Pesin's entropy formula
- Asymptotics of the upper matching conjecture
- Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures
- A simple proof of Wehrl's conjecture on entropy
- Randomly colouring graphs (a combinatorial view)
- An upper bound on the number of high-dimensional permutations
- A Tight Analysis of Bethe Approximation for Permanent
- Notes on use of generalized entropies in counting
- Further results on generalized conditional entropies
- Extremal graphs with a given number of perfect matchings
- Multidimensional permanents and an upper bound on the number of transversals in Latin squares
- An algorithmic proof of Brégman–Minc theorem
- Proof of a hypercontractive estimate via entropy
- Tight bounds on the coefficients of partition functions via stability
- The number of n-queens configurations
- Entropy bounds for perfect matchings and Hamiltonian cycles
- An entropy proof of the Kahn-Lovász theorem
- On the codimension of permanental varieties
- When entropy meets Turán: new proofs and hypergraph Turán results
- A tight analysis of Bethe approximation for permanent
- Partitioning the hypercube into smaller hypercubes
- A Billingsley type theorem for Bowen entropy
This page was built for publication: An entropy proof of Bregman's theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961543)
