Desigualdad de Bregman-Minc

En matemáticas discretas , la desigualdad de Bregman-Minc , o el teorema de Bregman , permite estimar el 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 probada por primera vez en 1973 por Lev M. Bregman . ^{[1] [2]} Alexander Schrijver y Jaikumar Radhakrishnan han proporcionado más pruebas basadas en la entropía . ^{[3] [4]} La desigualdad de Bregman-Minc se usa, por ejemplo, en teoría de grafos para obtener límites superiores para el número deCoincidencias perfectas en un gráfico bipartito .

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

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

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

De esta manera, cada entrada distinta de cero de la matriz define un borde en el gráfico y viceversa. Una combinación perfecta es una selección de aristas, de modo que cada vértice del gráfico es un punto final de una de estas aristas. Cada sumando distinto de cero del permanente de satisfacer${\ estilo de visualización A}$${\ estilo de visualización G}$${\ estilo de visualización G}$${\ estilo de visualización n}$${\ estilo de visualización A}$

Una matriz binaria y el gráfico bipartito correspondiente con una posible combinación perfecta marcada en rojo. De acuerdo con la desigualdad de Bregman-Minc, hay como máximo 18 coincidencias perfectas en este gráfico.