Bregman–Minc inequality

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.

Contents 1 Statement 2 Application 3 Related statements 4 See also 5 References 6 External links Statement 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} Aleq 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] Application 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.

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}=1Leftrightarrow {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_{1sigma (1)}cdots a_{nsigma (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] Related statements Using the inequality of arithmetic and geometric means, the Bregman–Minc inequality directly implies the weaker estimate {displaystyle operatorname {per} Aleq 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 _{Ain 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] See also Computing the permanent References ^ Henryk Minc (1963), "Upper bounds for permanents of (0,1)-matrices", Bull. Amer. Math. Soc., 69: 789–791, doi:10.1090/s0002-9904-1963-11031-9 ^ Lev Bregman (1973), "Some properties of nonnegative matrices and their permanents", Soviet Math. Dokl., 14: 945–949 ^ Alexander Schrijver (1978), "A short proof of Minc's conjecture", J. Combin. Theory Ser. A, 25: 80–83, doi:10.1016/0097-3165(78)90036-5 ^ Jaikumar Radhakrishnan (1997), "An entropy proof of Bregman's theorem", J. Combin. Theory Ser. A, 77: 161–164, doi:10.1006/jcta.1996.2727 ^ Jump up to: a b Henryk Minc (1984), Permanents, Encyclopedia of Mathematics and its Applications, vol. 6, Cambridge University Press, pp. 107–109 ^ Jump up to: a b Vladimir Sachkov (1996), Combinatorial Methods in Discrete Mathematics, Cambridge University Press, pp. 95–97 ^ Martin Aigner, Günter M. Ziegler (2015), Das Buch der Beweise (4. ed.), Springer, pp. 285–292 External links Robin Whitty. "Bregman's Theorem" (PDF; 274 KB). Theorem of the Day. Retrieved 19 October 2015. Categories: Theorems in discrete mathematics