Desigualdad de Bregman-Minc

En matemáticas discretas , la desigualdad de Bregman-Minc , o teorema de Bregman , permite estimar el permanente de una matriz binaria mediante las sumas de sus filas o columnas. La desigualdad fue conjeturada en 1963 por Henryk Minc y demostrada por primera vez en 1973 por Lev M. Bregman . ^{[ 1 ] [ 2 ]} Alexander Schrijver y Jaikumar Radhakrishnan han proporcionado demostraciones adicionales basadas en la entropía . ^{[ 3 ] [ 4 ]} La desigualdad de Bregman-Minc se utiliza, por ejemplo, en teoría de grafos para obtener cotas superiores para el número de emparejamientos perfectos en un grafo bipartito .

El permanente de una matriz binaria cuadrada${\displaystyle A=(a_{ij})}$de tamaño${\displaystyle n}$con sumas de filas${\displaystyle r_{i}=a_{i1}+\cdots +a_{in}}$para${\displaystyle i=1,\ldots ,n}$puede ser estimado por

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

Por lo tanto, el permanente está acotado por el producto de las medias geométricas de los números desde${\displaystyle 1}$a${\displaystyle r_{i}}$para${\displaystyle i=1,\ldots ,n}$La igualdad se cumple si la matriz es una matriz diagonal por bloques formada por matrices de unos o resulta de permutaciones de filas y/o columnas de dicha matriz diagonal por bloques. Dado que el permanente es invariante bajo transposición , la desigualdad también se cumple para las sumas de columnas de la matriz. ^{[ 5 ] [ 6 ]}

Existe una correspondencia uno a uno entre una matriz binaria cuadrada${\displaystyle A}$de tamaño${\displaystyle n}$y un grafo bipartito simple${\displaystyle G=(V\,{\dot {\cup }}\,W,E)}$con particiones de igual tamaño${\displaystyle V=\{v_{1},\ldots,v_{n}\}}$y${\displaystyle W=\{w_{1},\ldots,w_{n}\}}$tomando

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

De esta manera, cada entrada no nula de la matriz${\displaystyle A}$define una arista en el grafo${\displaystyle G}$y viceversa. Una combinación perfecta en${\displaystyle G}$es una selección de${\displaystyle n}$aristas, de tal manera que cada vértice del grafo es un extremo de una de estas aristas. Cada sumando no nulo del permanente de${\displaystyle A}$satisfactorio

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

corresponde a una coincidencia perfecta${\displaystyle \{\{v_{1},w_{\sigma (1)}\},\ldots ,\{v_{n},w_{\sigma (n)}\}\}}$de${\displaystyle G}$. Por lo tanto, si${\displaystyle {\mathcal {M}}(G)}$denota el conjunto de emparejamientos perfectos de${\displaystyle G}$,

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

se cumple. La desigualdad de Bregman-Minc ahora produce la estimación

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

dónde${\displaystyle d(v_{i})}$es el grado del vértice${\displaystyle v_{i}}$Debido a la simetría, la estimación correspondiente también es válida para${\displaystyle d(w_{i})}$en lugar de${\displaystyle d(v_{i})}$Por lo tanto, el número de posibles emparejamientos perfectos en un grafo bipartito con particiones de igual tamaño puede estimarse mediante los grados de los vértices de cualquiera de las dos particiones. ^{[ 7 ]}

Utilizando la desigualdad de las medias aritméticas y geométricas , la desigualdad de Bregman-Minc implica directamente la estimación más débil.

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

que fue probada por Henryk Minc ya en 1963. Otra consecuencia directa de la desigualdad de Bregman-Minc es una demostración de la siguiente conjetura de Herbert Ryser de 1960. Sea${\displaystyle k}$por un divisor de${\displaystyle n}$y dejar${\displaystyle \Lambda _{kn}}$denota el conjunto de matrices binarias cuadradas de tamaño${\displaystyle n}$con sumas de filas y columnas iguales a${\displaystyle k}$, entonces

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

El máximo se alcanza así para una matriz diagonal por bloques cuyos bloques diagonales son matrices cuadradas de unos de tamaño${\displaystyle k}$. Una declaración correspondiente para el caso que${\displaystyle k}$no es un divisor de${\displaystyle n}$es un problema matemático abierto. ^{[ 5 ] [ 6 ]}

• Calcular el permanente

• Robin Whitty. "Teorema de Bregman" (PDF; 274 KB) . Teorema del día . Consultado el 19 de octubre de 2015 .