The Bregman-Minc inequality is a result in discrete mathematics that bounds the permanent of a binary matrix using only its row or column sums. Henryk Minc conjectured the inequality in 1963, and Lev M. Bregman proved it in 1973, with further proofs based on entropy later given by Alexander Schrijver and Jaikumar Radhakrishnan. It is applied in graph theory, for instance to obtain upper bounds on the number of perfect matchings in a bipartite graph.
Facts
Classification
Statement Form Connections
Has Statement Form
In Branch
Source Bregman-Minc inequality (Wikipedia)
Principal Result Of
Source Henryk Minc (Wikipedia)
Source Lev M. Bregman (Wikipedia)
Proved By
Source Wikipedia: Bregman-Minc inequality
Sources
1. Wikipedia: Bregman-Minc inequality
WikipediaLead section, statement-form reference
In discrete mathematics, the Bregman-Minc inequality, or Bregman's theorem, allows one to estimate the permanent of a binary matrix via its row or column sums.
Proved By: Henryk Minc, Lead sentence
The inequality was conjectured in 1963 by Henryk Minc and first proved in 1973 by Lev M.
View the Source 2. Bregman-Minc inequality (Wikipedia)
Lead section
In discrete mathematics, the Bregman-Minc inequality, or Bregman's theorem, allows one to estimate the permanent of a binary matrix via its row or column sums.
In Branch: Combinatorics, Lead
In discrete mathematics, the Bregman-Minc inequality, or Bregman's theorem, allows one to estimate the permanent of a binary matrix
View the SourceHenryk Minc (Wikipedia)
Principal Result Of: Henryk Minc, Lead, Bregman-Minc inequalityQuote, Principal Result Of: Henryk Minc, Lead, Bregman-Minc inequality
Bregman-Minc inequality
Lev M. Bregman (Wikipedia)
Principal Result Of: Lev Bregman, Body, workQuote, Principal Result Of: Lev Bregman, Body, work
Bregman's Theorem, proving a 1963 conjecture of Henryk Minc, gives an upper bound on the permanent of a 0-1 matrix.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.