Bregman-Minc-Ungleichung

Bregman-Minc-Ungleichung In der diskreten Mathematik, die Bregman-Minc-Ungleichung, oder Satz von Bregman, ermöglicht es, die Permanente einer binären Matrix über ihre Zeilen- oder Spaltensummen abzuschätzen. Die Ungleichheit wurde vermutet 1963 von Henryk Minc und erstmals bewiesen in 1973 von Lew M. Bregmann.[1][2] Weitere entropiebasierte Beweise wurden von Alexander Schrijver und Jaikumar Radhakrishnan erbracht.[3][4] Es wird die Bregman-Minc-Ungleichung verwendet, zum Beispiel, in der Graphentheorie, um Obergrenzen für die Anzahl perfekter Übereinstimmungen in einem zweigeteilten Graphen zu erhalten.

Inhalt 1 Aussage 2 Anwendung 3 Verwandte Aussagen 4 Siehe auch 5 Verweise 6 External links Statement The permanent of a square binary matrix {Anzeigestil A=(a_{ij})} von Größe {Anzeigestil n} mit Zeilensummen {Anzeigestil r_{ich}=a_{i1}+cdots +a_{in}} zum {Anzeigestil i=1,ldots ,n} geschätzt werden kann {Anzeigestil Betreibername {pro} Aleq prod _{i=1}^{n}(r_{ich}!)^{1/r_{ich}}.} Die Permanente wird also durch das Produkt der geometrischen Mittel der Zahlen begrenzt {Anzeigestil 1} zu {Anzeigestil r_{ich}} zum {Anzeigestil i=1,ldots ,n} . Gleichheit gilt, wenn die Matrix eine Blockdiagonalmatrix ist, die aus Matrizen von Einsen besteht, oder sich aus Reihen- und/oder Spaltenpermutationen einer solchen Blockdiagonalmatrix ergibt. Da das Permanente unter Transposition invariant ist, die Ungleichung gilt entsprechend auch für die Spaltensummen der Matrix.[5][6] Anwendung Eine binäre Matrix und der zugehörige bipartite Graph mit einem möglichen perfekten Matching rot markiert. Gemäß der Bregman-Minc-Ungleichung, es gibt höchstens 18 perfekte Übereinstimmungen in diesem Diagramm.

Es gibt eine Eins-zu-Eins-Entsprechung zwischen einer quadratischen binären Matrix {Anzeigestil A} von Größe {Anzeigestil n} und ein einfacher bipartiter Graph {Anzeigestil G=(v,{Punkt {Tasse }},W,E)} mit gleichgroßen Partitionen {Anzeigestil V={v_{1},Punkte ,v_{n}}} und {Anzeigestil W ={w_{1},Punkte ,w_{n}}} indem {Anzeigestil a_{ij}=1Links-Rechts-Pfeil {v_{ich},w_{j}}in e.} Diesen Weg, jeder Nicht-Null-Eintrag der Matrix {Anzeigestil A} definiert eine Kante im Graphen {Anzeigestil G} und umgekehrt. Eine perfekte Einpassung {Anzeigestil G} ist eine Auswahl von {Anzeigestil n} Kanten, so dass jeder Knoten des Graphen ein Endpunkt einer dieser Kanten ist. Jeder Nicht-Null-Summand des Permanenten von {Anzeigestil A} befriedigend {Anzeigestil a_{1Sigma (1)}cdots a_{Es tut mir Leid (n)}=1} entspricht einem perfekten Matching {Anzeigestil {{v_{1},w_{Sigma (1)}},Punkte ,{v_{n},w_{Sigma (n)}}}} von {Anzeigestil G} . Deswegen, wenn {Anzeigestil {mathematisch {M}}(G)} bezeichnet die Menge der perfekten Matchings von {Anzeigestil G} , {Anzeigestil |{mathematisch {M}}(G)|= Betreibername {pro} EIN} hält. Die Bregman-Minc-Ungleichung liefert nun die Schätzung {Anzeigestil |{mathematisch {M}}(G)|leq prod _{i=1}^{n}(d(v_{ich})!)^{1/d(v_{ich})},} wo {Anzeigestil d(v_{ich})} ist der Grad des Scheitelpunkts {Anzeigestil v_{ich}} . Wegen Symmetrie, die entsprechende Abschätzung gilt auch für {Anzeigestil d(w_{ich})} Anstatt von {Anzeigestil d(v_{ich})} . Die Anzahl möglicher perfekter Übereinstimmungen in einem bipartiten Graphen mit gleichgroßen Partitionen kann daher über die Grade der Knoten jeder der beiden Partitionen geschätzt werden.[7] Related statements Using the inequality of arithmetic and geometric means, die Bregman-Minc-Ungleichung impliziert direkt die schwächere Schätzung {Anzeigestil Betreibername {pro} Aleq prod _{i=1}^{n}{frac {r_{ich}+1}{2}},} was bereits von Henryk Minc bewiesen wurde 1963. Eine weitere direkte Folge der Bregman-Minc-Ungleichung geht aus einem Beweis der folgenden Vermutung von Herbert Ryser hervor 1960. Lassen {Anzeigestil k} durch einen Teiler von {Anzeigestil n} und lass {Anzeigestil Lambda _{kn}} bezeichnen die Menge der quadratischen binären Matrizen der Größe {Anzeigestil n} mit Zeilen- und Spaltensummen gleich {Anzeigestil k} , dann {Anzeigestil max _{Ain Lambda _{kn}}Name des Bedieners {pro} A=(k!)^{n/k}.} Das Maximum wird dabei für eine Blockdiagonalmatrix erreicht, deren Diagonalblöcke quadratische Matrizen der Größe Einsen sind {Anzeigestil k} . Eine entsprechende Aussage für den Fall, dass {Anzeigestil k} ist kein Teiler von {Anzeigestil n} ist ein offenes mathematisches Problem.[5][6] Siehe auch Berechnung der permanenten Referenzen ^ Henryk Minc (1963), "Obergrenzen für bleibende Zahlen von (0,1)-Matrizen", Stier. Amer. Mathematik. Soc., 69: 789–791, doi:10.1090/s0002-9904-1963-11031-9 ^ Lev Bregman (1973), "Einige Eigenschaften nichtnegativer Matrizen und ihrer Permanenten", Sowjetische Mathematik. Bis um, 14: 945–949 ^ Alexander Schriftsteller (1978), "Ein kurzer Beweis von Mincs Vermutung", J. kombinieren. Theorie Ser. EIN, 25: 80–83, doi:10.1016/0097-3165(78)90036-5 ^ Jaikumar Radhakrishnan (1997), "Ein Entropiebeweis des Satzes von Bregman", J. kombinieren. Theorie Ser. EIN, 77: 161–164, doi:10.1006/jcta.1996.2727 ^ Hochspringen zu: a b Henryk Minc (1984), Dauerhaft, Enzyklopädie der Mathematik und ihrer Anwendungen, vol. 6, Cambridge University Press, pp. 107–109 ^ Jump up to: a b Wladimir Sachkow (1996), Kombinatorische Methoden in der diskreten Mathematik, Cambridge University Press, pp. 95–97 ^ Martin Aigner, Günter M. Ziegler (2015), Das Buch der Beweise (4. ed.), Springer, pp. 285–292 External links Robin Whitty. "Satz von Bregman" (Pdf; 274 KB). Theorem des Tages. Abgerufen 19 Oktober 2015. Kategorien: Theoreme in der diskreten Mathematik