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 probada por primera vez en 1973 por Lev M. Bregman . [1] [2] Otros entropía pruebas basadas han sido dadas por Alexander Schrijver y Jaikumar Radhakrishnan . [3] [4] La desigualdad de Bregman-Minc se utiliza, por ejemplo, en la teoría de grafos para obtener los límites superiores del número deemparejamientos perfectos en un gráfico bipartito .
Declaración
El permanente de una matriz binaria cuadrada de tamaño con sumas de fila por puede ser estimado por
Por lo tanto, el permanente está acotado por el producto de las medias geométricas de los números de a por . La igualdad es válida 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 transposición , la desigualdad también es válida para las sumas de columna de la matriz en consecuencia. [5] [6]
Solicitud
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/8/82/Perfect_matching_qtl1.svg/310px-Perfect_matching_qtl1.svg.png)
Existe una correspondencia uno a uno entre una matriz binaria cuadrada de tamaño y un gráfico bipartito simplecon particiones de igual tamaño y tomando
De esta forma, cada entrada distinta de cero de la matriz define un borde en el gráficoy viceversa. Una combinación perfecta en es una selección de aristas, de modo que cada vértice del gráfico sea un punto final de una de estas aristas. Cada sumando distinto de cero del permanente de satisfactorio
corresponde a una combinación perfecta de . Por tanto, si denota el conjunto de combinaciones perfectas de ,
sostiene. La desigualdad de Bregman-Minc ahora arroja la estimación
dónde es el grado del vértice. Debido a la simetría, la estimación correspondiente también es válida para en vez de . Por lo tanto, el número de posibles coincidencias perfectas en un gráfico bipartito con particiones de igual tamaño se puede estimar mediante los grados de los vértices de cualquiera de las dos particiones. [7]
Declaraciones relacionadas
Usando la desigualdad de medias aritméticas y geométricas , la desigualdad de Bregman-Minc implica directamente la estimación más débil
que fue probado por Henryk Minc ya en 1963. Otra consecuencia directa de la desigualdad de Bregman-Minc es una prueba de la siguiente conjetura de Herbert Ryser de 1960. Sea por un divisor de y deja denotar el conjunto de matrices binarias cuadradas de tamaño con sumas de filas y columnas iguales a , luego
De este modo, se alcanza el máximo para una matriz diagonal de bloques cuyos bloques diagonales son matrices cuadradas de un tamaño . Una declaración correspondiente para el caso de que no es un divisor de es un problema matemático abierto. [5] [6]
Ver también
Referencias
- ^ Henryk Minc (1963), "Límites superiores para permanentes de (0,1) -matrices", Bull. Amer. Matemáticas. Soc. , 69 : 789–791, doi : 10.1090 / s0002-9904-1963-11031-9
- ^ Lev Bregman (1973), "Algunas propiedades de matrices no negativas y sus permanentes", Matemáticas soviéticas. Dokl. , 14 : 945–949
- ^ Alexander Schrijver (1978), "Una breve prueba de la conjetura de Minc" , J. Combin. Teoría Ser. A , 25 : 80–83, doi : 10.1016 / 0097-3165 (78) 90036-5
- ^ 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
- ^ a b Henryk Minc (1984), Permanentes , Enciclopedia de las matemáticas y sus aplicaciones, 6 , Cambridge University Press, págs. 107-109
- ^ a b Vladimir Sachkov (1996), Métodos combinatorios en matemáticas discretas , Cambridge University Press, págs. 95–97
- ^ Martin Aigner, Günter M. Ziegler (2015), Das Buch der Beweise (4. ed.), Springer, págs. 285–292
enlaces externos
- Robin Whitty. "Teorema de Bregman" (PDF; 274 KB) . Teorema del día . Consultado el 19 de octubre de 2015 .