page_title: Bregman–Minc inequality
section_title: Application
hierarchical_section_title: Bregman–Minc inequality / Application
context_page_description: 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. The inequality was conjectured in 1963 by Henryk Minc and first proved in 1973 by Lev M. Bregman. Further entropy-based proofs have been given by Alexander Schrijver and Jaikumar Radhakrishnan. The Bregman–Minc inequality is used, for example, in graph theory to obtain upper bounds for the number of perfect matchings in a bipartite graph.
context_section_description: There is a one-to-one correspondence between a square binary matrix  of size  and a simple bipartite graph  with equal-sized partitions  and  by taking
  This way, each nonzero entry of the matrix  defines an edge in the graph  and vice versa. A perfect matching in  is a selection of  edges, such that each vertex of the graph is an endpoint of one of these edges. Each nonzero summand of the permanent of  satisfying
  corresponds to a perfect matching  of . Therefore, if  denotes the set of perfect matchings of ,
  holds. The Bregman–Minc inequality now yields the estimate
  where  is the degree of the vertex . Due to symmetry, the corresponding estimate also holds for  instead of . The number of possible perfect matchings in a bipartite graph with equal-sized partitions can therefore be estimated via the degrees of the vertices of any of the two partitions.
caption: A binary matrix and the corresponding bipartite graph with a possible perfect matching marked in red. According to the Bregman–Minc inequality, there are at most 18 perfect matchings in this graph.