Disuguaglianza di Bregman-Minc

Disuguaglianza di Bregman-Minc nella matematica discreta, la disuguaglianza di Bregman-Minc, o il teorema di Bregman, consente di stimare il permanente di una matrice binaria tramite le sue somme di righe o colonne. La disuguaglianza è stata ipotizzata 1963 di Henryk Minc e si è presentato per la prima volta 1973 di Lev M. Bregmann.[1][2] Ulteriori prove basate sull'entropia sono state fornite da Alexander Schrijver e Jaikumar Radhakrishnan.[3][4] Viene utilizzata la disuguaglianza di Bregman-Minc, Per esempio, nella teoria dei grafi per ottenere limiti superiori per il numero di abbinamenti perfetti in un grafo bipartito.

Contenuti 1 Dichiarazione 2 Applicazione 3 Dichiarazioni correlate 4 Guarda anche 5 Riferimenti 6 External links Statement The permanent of a square binary matrix {stile di visualizzazione A=(un_{ij})} di taglia {stile di visualizzazione n} con somme di riga {stile di visualizzazione r_{io}=a_{i1}+cdot +a_{in}} per {displaystyle i=1,ldots ,n} può essere stimato da {nome dell'operatore dello stile di visualizzazione {per} Aleq prod _{io=1}^{n}(r_{io}!)^{1/r_{io}}.} Il permanente è quindi delimitato dal prodotto delle medie geometriche dei numeri da {stile di visualizzazione 1} a {stile di visualizzazione r_{io}} per {displaystyle i=1,ldots ,n} . L'uguaglianza vale se la matrice è una matrice diagonale a blocchi costituita da matrici di uno o risulta da permutazioni di riga e/o colonna di tale matrice diagonale a blocchi. Poiché il permanente è invariante in fase di trasposizione, la disuguaglianza vale anche per le somme delle colonne della matrice di conseguenza.[5][6] Applicazione Una matrice binaria e il corrispondente grafo bipartito con un possibile abbinamento perfetto segnato in rosso. Secondo la disuguaglianza di Bregman-Minc, ci sono al massimo 18 corrispondenze perfette in questo grafico.

Esiste una corrispondenza biunivoca tra una matrice binaria quadrata {stile di visualizzazione A} di taglia {stile di visualizzazione n} e un semplice grafo bipartito {stile di visualizzazione G=(V,{punto {tazza }},w,e)} con partizioni di uguale dimensione {stile di visualizzazione V={v_{1},ldot ,v_{n}}} e {stile di visualizzazione W ={w_{1},ldot ,w_{n}}} prendendo {stile di visualizzazione a_{ij}=1freccia sinistra destra {v_{io},w_{j}}in e.} Per di qua, ogni voce diversa da zero della matrice {stile di visualizzazione A} definisce un bordo nel grafico {stile di visualizzazione G} e viceversa. Un perfetto abbinamento {stile di visualizzazione G} è una selezione di {stile di visualizzazione n} bordi, in modo tale che ogni vertice del grafo sia un punto finale di uno di questi archi. Ogni somma diversa da zero del permanente di {stile di visualizzazione A} soddisfacente {stile di visualizzazione a_{1sigma (1)}cdots a_{Mi dispiace (n)}=1} corrisponde ad un abbinamento perfetto {stile di visualizzazione {{v_{1},w_{sigma (1)}},ldot ,{v_{n},w_{sigma (n)}}}} di {stile di visualizzazione G} . Perciò, Se {stile di visualizzazione {matematico {M}}(G)} denota l'insieme degli abbinamenti perfetti di {stile di visualizzazione G} , {stile di visualizzazione |{matematico {M}}(G)|=nome operatore {per} UN} tiene. La disuguaglianza di Bregman-Minc ora fornisce la stima {stile di visualizzazione |{matematico {M}}(G)|leq prod _{io=1}^{n}(d(v_{io})!)^{1/d(v_{io})},} dove {stile di visualizzazione d(v_{io})} è il grado del vertice {stile di visualizzazione v_{io}} . Per simmetria, vale anche la stima corrispondente {stile di visualizzazione d(w_{io})} invece di {stile di visualizzazione d(v_{io})} . Il numero di possibili abbinamenti perfetti in un grafo bipartito con partizioni di uguale dimensione può quindi essere stimato tramite i gradi dei vertici di una qualsiasi delle due partizioni.[7] Related statements Using the inequality of arithmetic and geometric means, la disuguaglianza di Bregman-Minc implica direttamente la stima più debole {nome dell'operatore dello stile di visualizzazione {per} Aleq prod _{io=1}^{n}{frac {r_{io}+1}{2}},} che è stato dimostrato da Henryk Minc già presente 1963. Un'altra conseguenza diretta della disuguaglianza di Bregman-Minc è una prova della seguente congettura di Herbert Ryser da 1960. Permettere {stile di visualizzazione k} da un divisore di {stile di visualizzazione n} e lascia {displaystyle Lambda _{kn}} denotiamo l'insieme delle matrici binarie quadrate di dimensione {stile di visualizzazione n} con somma di righe e colonne pari a {stile di visualizzazione k} , poi {stile di visualizzazione massimo _{Ain Lambda _{kn}}nome operatore {per} A=(K!)^{n/k}.} Il massimo è quindi raggiunto per una matrice diagonale a blocchi i cui blocchi diagonali sono matrici quadrate di dimensioni uguali {stile di visualizzazione k} . Una dichiarazione corrispondente per il caso che {stile di visualizzazione k} non è un divisore di {stile di visualizzazione n} è un problema matematico aperto.[5][6] Vedi anche Calcolo dei riferimenti permanenti ^ Henryk Minc (1963), "Limiti superiori per i permanenti di (0,1)-matrici", Toro. Amer. Matematica. soc., 69: 789–791, doi:10.1090/s0002-9904-1963-11031-9 ^ Lev Bregman (1973), "Alcune proprietà delle matrici non negative e dei loro permanenti", Matematica sovietica. Fino a quando, 14: 945–949 ^ Alessandro scrittore (1978), "Una breve dimostrazione della congettura di Minc", J. combinare. Teoria ser. UN, 25: 80–83, doi:10.1016/0097-3165(78)90036-5 ^ Jaikumar Radhakrishnan (1997), "Una dimostrazione entropica del teorema di Bregman", J. combinare. Teoria ser. UN, 77: 161–164, doi:10.1006/jcta.1996.2727 ^ Salta su: a b Henryk Minc (1984), Permanente, Enciclopedia della matematica e sue applicazioni, vol. 6, Cambridge University Press, pp. 107–109 ^ Jump up to: a b Vladimir Sachkov (1996), Metodi Combinatoriali in Matematica Discreta, Cambridge University Press, pp. 95–97 ^ Martin Aigner, Gunter M. Ziegler (2015), Il libro dell'evidenza (4. ed.), Springer, pp. 285–292 External links Robin Whitty. "Teorema di Bregman" (PDF; 274 KB). Teorema del giorno. Recuperato 19 ottobre 2015. Categorie: Teoremi in matematica discreta