Inégalité de Bregman-Minc

Inégalité de Bregman-Minc En mathématiques discrètes, l'inégalité de Bregman-Minc, ou le théorème de Bregman, permet d'estimer le permanent d'une matrice binaire via ses sommes lignes ou colonnes. L'inégalité a été conjecturée dans 1963 par Henryk Minc et prouvé pour la première fois en 1973 par Lev M. Bregman.[1][2] D'autres preuves basées sur l'entropie ont été données par Alexander Schrijver et Jaikumar Radhakrishnan.[3][4] L'inégalité de Bregman-Minc est utilisée, par exemple, en théorie des graphes pour obtenir des bornes supérieures pour le nombre d'appariements parfaits dans un graphe biparti.

Contenu 1 Déclaration 2 Application 3 Déclarations connexes 4 Voir également 5 Références 6 Liens externes Énoncé Le permanent d'une matrice binaire carrée {style d'affichage A=(un_{ij})} de taille {displaystyle n} avec des sommes de lignes {style d'affichage r_{je}=a_{i1}+cdots +a_{dans}} pour {style d'affichage i=1,ldots ,n} peut être estimé par {nom de l'opérateur de style d'affichage {par} Produit Aleq _{je=1}^{n}(r_{je}!)^{1/r_{je}}.} Le permanent est donc borné par le produit des moyennes géométriques des nombres de {style d'affichage 1} à {style d'affichage r_{je}} pour {style d'affichage i=1,ldots ,n} . L'égalité est valable si la matrice est une matrice diagonale de blocs composée de matrices de uns ou de résultats de permutations de lignes et / ou de colonnes d'une telle matrice diagonale de blocs. Puisque le permanent est invariant par transposition, l'inégalité est également valable pour les sommes des colonnes de la matrice en conséquence.[5][6] Application Une matrice binaire et le graphe biparti correspondant avec un appariement parfait possible marqué en rouge. D'après l'inégalité de Bregman-Minc, il y a au maximum 18 correspondances parfaites dans ce graphique.

Il existe une correspondance biunivoque entre une matrice binaire carrée {style d'affichage A} de taille {displaystyle n} et un graphe biparti simple {style d'affichage G=(V,{point {Coupe }},O,E)} avec des cloisons de taille égale {style d'affichage V={v_{1},ldots ,v_{n}}} et {style d'affichage W ={w_{1},ldots ,w_{n}}} en prenant {style d'affichage a_{ij}=1Gauchedroiteflèche {v_{je},w_{j}}dans E.} Par ici, chaque entrée non nulle de la matrice {style d'affichage A} définit une arête dans le graphe {style d'affichage G} et vice versa. Une parfaite adéquation dans {style d'affichage G} est une sélection de {displaystyle n} bords, tel que chaque sommet du graphe soit une extrémité de l'une de ces arêtes. Chaque sommation non nulle du permanent de {style d'affichage A} satisfaisant {style d'affichage a_{1sigma (1)}cdots a_{Je suis désolé (n)}=1} correspond à un appariement parfait {style d'affichage {{v_{1},w_{sigma (1)}},ldots ,{v_{n},w_{sigma (n)}}}} de {style d'affichage G} . Par conséquent, si {style d'affichage {mathématique {M}}(g)} désigne l'ensemble des appariements parfaits de {style d'affichage G} , {style d'affichage |{mathématique {M}}(g)|=nomopérateur {par} UN} détient. L'inégalité de Bregman-Minc donne maintenant l'estimation {style d'affichage |{mathématique {M}}(g)|prod leq _{je=1}^{n}(ré(v_{je})!)^{1/ré(v_{je})},} où {displaystyle d(v_{je})} est le degré du sommet {style d'affichage v_{je}} . En raison de la symétrie, l'estimation correspondante vaut également pour {displaystyle d(w_{je})} à la place de {displaystyle d(v_{je})} . Le nombre d'appariements parfaits possibles dans un graphe biparti avec des partitions de taille égale peut donc être estimé via les degrés des sommets de l'une des deux partitions.[7] Énoncés connexes Utilisation de l'inégalité des moyennes arithmétiques et géométriques, l'inégalité de Bregman – Minc implique directement l'estimation la plus faible {nom de l'opérateur de style d'affichage {par} Produit Aleq _{je=1}^{n}{frac {r_{je}+1}{2}},} qui a été prouvé par Henryk Minc déjà en 1963. Une autre conséquence directe de l'inégalité de Bregman-Minc est une preuve de la conjecture suivante de Herbert Ryser de 1960. Laisser {style d'affichage k} par un diviseur de {displaystyle n} et laissez {style d'affichage Lambda _{kn}} désignent l'ensemble des matrices binaires carrées de taille {displaystyle n} avec des sommes de ligne et de colonne égales à {style d'affichage k} , alors {style d'affichage max _{Aïn Lambda _{kn}}nom de l'opérateur {par} A=(k!)^{n/k}.} Le maximum est ainsi atteint pour une matrice diagonale par blocs dont les blocs diagonaux sont des matrices carrées de ceux de taille {style d'affichage k} . Une déclaration correspondante pour le cas où {style d'affichage k} n'est pas un diviseur de {displaystyle n} est un problème mathématique ouvert.[5][6] Voir aussi Calcul des références permanentes ^ Henryk Minc (1963), "Limites supérieures pour les permanents de (0,1)-matrices", Taureau. Amer. Math. Soc., 69: 789–791, est ce que je:10.1090/s0002-9904-1963-11031-9 ^ Lev Bregman (1973), "Quelques propriétés des matrices non négatives et de leurs permanents", Mathématiques soviétiques. Jusqu'à, 14: 945–949 ^ Alexandre Écrivain (1978), "Une courte preuve de la conjecture de Minc", J. combiner. Théorie Ser. UN, 25: 80–83, est ce que je:10.1016/0097-3165(78)90036-5 ^ Jaikumar Radhakrishnan (1997), "Une preuve entropique du théorème de Bregman", J. combiner. Théorie Ser. UN, 77: 161–164, est ce que je:10.1006/jcta.1996.2727 ^ Sauter à: a b Henryk Minc (1984), Permanents, Encyclopédie des mathématiques et de ses applications, volume. 6, la presse de l'Universite de Cambridge, pp. 107–109 ^ Passer à: a b Vladimir Sachkov (1996), Méthodes combinatoires en mathématiques discrètes, la presse de l'Universite de Cambridge, pp. 95–97 ^ Martin Aigner, Günter M. Ziegler (2015), Le livre des preuves (4. éd.), Springer, pp. 285–292 Liens externes Robin Whitty. "Théorème de Bregman" (PDF; 274 Ko). Théorème du jour. Récupéré 19 Octobre 2015. Catégories: Théorèmes en mathématiques discrètes