Английская Википедия: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.
Statement
The permanent of a square binary matrix <math>A = (a_{ij})</math> of size <math>n</math> with row sums <math>r_i = a_{i1} + \cdots + a_{in}</math> for <math>i=1, \ldots , n</math> can be estimated by
- <math>\operatorname{per}A \leq \prod_{i=1}^n (r_i!)^{1/r_i}.</math>
The permanent is therefore bounded by the product of the geometric means of the numbers from <math>1</math> to <math>r_i</math> for <math>i=1, \ldots , n</math>. 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
There is a one-to-one correspondence between a square binary matrix <math>A</math> of size <math>n</math> and a simple bipartite graph <math>G = (V \, \dot\cup \, W, E)</math> with equal-sized partitions <math>V = \{ v_1, \ldots , v_n \}</math> and <math>W = \{ w_1, \ldots , w_n \}</math> by taking
- <math>a_{ij} = 1 \Leftrightarrow \{ v_i, w_j \} \in E.</math>
This way, each nonzero entry of the matrix <math>A</math> defines an edge in the graph <math>G</math> and vice versa. A perfect matching in <math>G</math> is a selection of <math>n</math> edges, such that each vertex of the graph is an endpoint of one of these edges. Each nonzero summand of the permanent of <math>A</math> satisfying
- <math>a_{1\sigma(1)} \cdots a_{n\sigma(n)} = 1</math>
corresponds to a perfect matching <math>\{ \{ v_1, w_{\sigma(1)} \}, \ldots , \{ v_n, w_{\sigma(n)} \} \}</math> of <math>G</math>. Therefore, if <math>\mathcal{M}(G)</math> denotes the set of perfect matchings of <math>G</math>,
- <math>| \mathcal{M}(G) | = \operatorname{per}A</math>
holds. The Bregman–Minc inequality now yields the estimate
- <math>| \mathcal{M}(G) | \leq \prod_{i=1}^n (d(v_i)!)^{1/d(v_i)},</math>
where <math>d(v_i)</math> is the degree of the vertex <math>v_i</math>. Due to symmetry, the corresponding estimate also holds for <math>d(w_i)</math> instead of <math>d(v_i)</math>. 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
- <math>\operatorname{per}A \leq \prod_{i=1}^n \frac{r_i+1}{2},</math>
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 <math>k</math> by a divisor of <math>n</math> and let <math>\Lambda_{kn}</math> denote the set of square binary matrices of size <math>n</math> with row and column sums equal to <math>k</math>, then
- <math>\max_{A \in \Lambda_{kn}} \operatorname{per}A = (k!)^{n/k}.</math>
The maximum is thereby attained for a block diagonal matrix whose diagonal blocks are square matrices of ones of size <math>k</math>. A corresponding statement for the case that <math>k</math> is not a divisor of <math>n</math> is an open mathematical problem.[5][6]
See also
References
External links
- ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокminc69
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокbregman
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокschrijver
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокradhakrishnan
не указан текст - ↑ 5,0 5,1 Ошибка цитирования Неверный тег
<ref>
; для сносокminc
не указан текст - ↑ 6,0 6,1 Ошибка цитирования Неверный тег
<ref>
; для сносокsachkov
не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>
; для сносокaigner
не указан текст