Bregman–Minc inequality

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.^[1][2] Further entropy-based proofs have been given by Alexander Schrijver and Jaikumar Radhakrishnan.^[3][4] 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.

The permanent of a square binary matrix ${\displaystyle A=(a_{ij})}$ of size ${\displaystyle n}$ with row sums ${\displaystyle r_{i}=a_{i1}+\cdots +a_{in}}$ for ${\displaystyle i=1,\ldots ,n}$ can be estimated by

${\displaystyle \operatorname {per} A\leq \prod _{i=1}^{n}(r_{i}!)^{1/r_{i}}.}$

The permanent is therefore bounded by the product of the geometric means of the numbers from ${\displaystyle 1}$ to ${\displaystyle r_{i}}$ for ${\displaystyle i=1,\ldots ,n}$. Equality holds if the matrix is a block diagonal matrix consisting of matrices of ones or results from row and/or column permutations of such a block diagonal matrix. Since the permanent is invariant under transposition, the inequality also holds for the column sums of the matrix accordingly.^[5][6]

There is a one-to-one correspondence between a square binary matrix ${\displaystyle A}$ of size ${\displaystyle n}$ and a simple bipartite graph ${\displaystyle G=(V\,{\dot {\cup }}\,W,E)}$ with equal-sized partitions ${\displaystyle V=\{v_{1},\ldots ,v_{n}\}}$ and ${\displaystyle W=\{w_{1},\ldots ,w_{n}\}}$ by taking

${\displaystyle a_{ij}=1\Leftrightarrow \{v_{i},w_{j}\}\in E.}$

This way, each nonzero entry of the matrix ${\displaystyle A}$ defines an edge in the graph ${\displaystyle G}$ and vice versa. A perfect matching in ${\displaystyle G}$ is a selection of ${\displaystyle n}$ edges, such that each vertex of the graph is an endpoint of one of these edges. Each nonzero summand of the permanent of ${\displaystyle A}$ satisfying

${\displaystyle a_{1\sigma (1)}\cdots a_{n\sigma (n)}=1}$

corresponds to a perfect matching ${\displaystyle \{\{v_{1},w_{\sigma (1)}\},\ldots ,\{v_{n},w_{\sigma (n)}\}\}}$ of ${\displaystyle G}$. Therefore, if ${\displaystyle {\mathcal {M}}(G)}$ denotes the set of perfect matchings of ${\displaystyle G}$,

${\displaystyle |{\mathcal {M}}(G)|=\operatorname {per} A}$

holds. The Bregman–Minc inequality now yields the estimate

${\displaystyle |{\mathcal {M}}(G)|\leq \prod _{i=1}^{n}(d(v_{i})!)^{1/d(v_{i})},}$

where ${\displaystyle d(v_{i})}$ is the degree of the vertex ${\displaystyle v_{i}}$. Due to symmetry, the corresponding estimate also holds for ${\displaystyle d(w_{i})}$ instead of ${\displaystyle d(v_{i})}$. 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.^[7]

Using the inequality of arithmetic and geometric means, the Bregman–Minc inequality directly implies the weaker estimate

${\displaystyle \operatorname {per} A\leq \prod _{i=1}^{n}{\frac {r_{i}+1}{2}},}$

which was proven by Henryk Minc already in 1963. Another direct consequence of the Bregman–Minc inequality is a proof of the following conjecture of Herbert Ryser from 1960. Let ${\displaystyle k}$ by a divisor of ${\displaystyle n}$ and let ${\displaystyle \Lambda _{kn}}$ denote the set of square binary matrices of size ${\displaystyle n}$ with row and column sums equal to ${\displaystyle k}$, then

${\displaystyle \max _{A\in \Lambda _{kn}}\operatorname {per} A=(k!)^{n/k}.}$

The maximum is thereby attained for a block diagonal matrix whose diagonal blocks are square matrices of ones of size ${\displaystyle k}$. A corresponding statement for the case that ${\displaystyle k}$ is not a divisor of ${\displaystyle n}$ is an open mathematical problem.^[5][6]

• Computing the permanent

• Robin Whitty. "Bregman's Theorem" (PDF; 274 KB). Theorem of the Day. Retrieved 19 October 2015.