Desigualdad de Bregman-Minc

En matemáticas discretas , la desigualdad de Bregman-Minc , o teorema de Bregman , permite estimar la permanente de una matriz binaria a través de sus sumas de 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 otras demostraciones basadas en la entropía . ^{[3] [4]} La desigualdad de Bregman-Minc se utiliza, por ejemplo, en la teoría de grafos para obtener límites superiores para el número de emparejamientos perfectos en un grafo bipartito .

Declaración

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

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

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

Solicitud

Matriz binaria y su correspondiente grafo bipartito con un posible emparejamiento perfecto marcado en rojo. Según la desigualdad de Bregman-Minc, en este grafo hay como máximo 18 emparejamientos perfectos.

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

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

De esta manera, cada entrada distinta de cero de la matriz define una arista en el grafo y viceversa. Una correspondencia perfecta es una selección de aristas, de modo que cada vértice del grafo es un punto final de una de estas aristas. Cada sumando distinto de cero del permanente de satisface ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle A}$

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

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

${\displaystyle |{\mathcal {M}}(G)|=\operatorname {per} 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})},}$

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

Declaraciones relacionadas

Utilizando la desigualdad de 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}},}$

lo cual fue demostrado 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 por un divisor de y sea el conjunto de matrices binarias cuadradas de tamaño con sumas de filas y columnas iguales a , entonces ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle \Lambda _{kn}}$ ${\displaystyle n}$ ${\displaystyle k}$

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

De este modo se alcanza el máximo para una matriz diagonal de bloques cuyos bloques diagonales son matrices cuadradas de unos de tamaño . Un enunciado correspondiente para el caso en el que no es divisor de es un problema matemático abierto. ^{[5] [6]} ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$

Véase también

• Calculando el permanente

Referencias

1. Henryk Minc (1963), "Límites superiores para permanentes de matrices (0,1)", Bull. Amer. Math. Soc. , 69 : 789–791, doi : 10.1090/s0002-9904-1963-11031-9
2. Lev Bregman (1973), "Algunas propiedades de matrices no negativas y sus permanentes", Soviet Math. Dokl. , 14 : 945–949
3. Alexander Schrijver (1978), "Una breve prueba de la conjetura de Minc", J. Combin. Theory Ser. A , 25 : 80–83, doi : 10.1016/0097-3165(78)90036-5
4. Jaikumar Radhakrishnan (1997), "Una prueba de entropía del teorema de Bregman", J. Combin. Teoría Ser. A , 77 : 161–164, doi : 10.1006/jcta.1996.2727
5. Henryk Minc (1984), Permanentes , Enciclopedia de matemáticas y sus aplicaciones, vol. 6, Cambridge University Press, págs. 107-109
6. Vladimir Sachkov (1996), Métodos combinatorios en matemáticas discretas , Cambridge University Press, págs. 95-97
7. Martin Aigner, Günter M. Ziegler (2015), Das Buch der Beweise (4. ed.), Springer, págs.

Enlaces externos

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