Nierówność Bregmana-Minca

W matematyce dyskretnej nierówność Bregmana – Minca lub twierdzenie Bregmana pozwala oszacować trwałość macierzy binarnej na podstawie sum jej wierszy lub kolumn. Nierówność została wysunięta w 1963 roku przez Henryka Minca i po raz pierwszy udowodniona w 1973 roku przez Leva M. Bregmana . Dalsze entropii zostały podane przez Alexandra Schrijvera i Jaikumara Radhakrishnana . Nierówność Bregmana – Minca jest używana na przykład w teorii grafów do uzyskania górnych granic liczby doskonałych dopasowań na grafie dwudzielnym .

Oświadczenie

Stała $_ \ Displaystyle r_ {i} = a_ {i1} + \ cdots + a_ {w}}$ o $ja$ z $wierszy$ dla ${\ Displaystyle i = 1, \ ldots, n}$ można oszacować przez

${\ Displaystyle \ nazwa operatora {per} A \ równoważnik \ prod _ {i = 1} ^ {n} (r_ {i}!) ^ {1/r_ {i}}.}$

Trwałość jest zatem ograniczona iloczynem średnich geometrycznych liczb od do ${\$$displaystyle r_ {i}}$ dla $,n}$${\ displaystyle i = 1, \$ . Równość zachodzi, jeśli macierz jest macierzą diagonalną blokową składającą się z macierzy jedności lub wynika z permutacji wierszy i / lub kolumn takiej macierzy diagonalnej bloków. Ponieważ permanent jest niezmienny w transpozycji , nierówność obowiązuje również odpowiednio dla sum kolumn macierzy.

Aplikacja

Macierz binarna i odpowiadający jej wykres dwudzielny z możliwym idealnym dopasowaniem zaznaczonym na czerwono. Zgodnie z nierównością Bregmana – Minca na tym wykresie jest co najwyżej 18 idealnych dopasowań.

Istnieje zgodność jeden do jednego między kwadratową macierzą binarną $a$ rozmiarze prostym wykresem dwudzielnym $sol$$\, {\ kropka {\ filiżanka}} \, W, E}}$$\ Displaystyle G = ($ z równymi partycjami $}$${\ Displaystyle V = \ {v_ {1}, \ ldots, v_ {$$_$ i _

${\ Displaystyle a_ {ij} = 1 \ strzałka w lewo \ {v_ {i}, w_ {j} \} \ w E.}$

$W ten sposób$$niezerowy$ wpis macierzy definiuje krawędź na wykresie odwrotnie. Idealne dopasowanie w $to$ wybór $jest$ , tak że każdy wykresu punktem końcowym jednej z tych krawędzi. Każda niezerowa suma $satysfakcjonująca$

${\ Displaystyle a_ {1 \ sigma (1)} \ cdots a_ {n \ sigma (n)} = 1}$

$_ \} \ ldots, \ {v_ {n}, w _ {\ sigma (n)} \} \}}$ idealnemu z ${\ displaystyle G}$ . Dlatego też, jeśli oznacza zbiór doskonałych dopasowań , $\ Displaystyle {\$$mathcal {M}} (G)$ }

${\ Displaystyle | {\ mathcal {M}} (G) | = \ operatorname {per} A}$

posiada. Nierówność Bregmana – Minca daje teraz oszacowanie

${\ Displaystyle | {\ mathcal {M}} (G) | \ równoważnik \ prod _ {i = 1} ^ {n }(d(v_{i})!)^{1/d(v_{i})},}$

gdzie ${\ Displaystyle d (v_ {i})}$ jest stopniem wierzchołka ${\ displaystyle v_ {i}}$ . ${i}$ oszacowanie obowiązuje również dla ) $v_$ ) Liczbę możliwych idealnych dopasowań w grafie dwudzielnym z partycjami o równej wielkości można zatem oszacować na podstawie stopni wierzchołków dowolnego z dwóch partycji.

Powiązane stwierdzenia

Korzystając z nierówności średnich arytmetycznych i geometrycznych , nierówność Bregmana-Minc bezpośrednio implikuje słabsze oszacowanie

${\ Displaystyle \ operatorname {per} A \ równoważnik \ prod _ {i = 1} ^ {n} {\ Frac {r_ {i} + 1} 2}},}$

co udowodnił Henryk Minc już w 1963 roku. Inną bezpośrednią konsekwencją nierówności Bregmana – Minca jest dowód $następującego$$.$ Herberta z 1960 roku niech oznacza zbiór kwadratowych macierzy binarnych o rozmiarze ${\ Displaystyle k}$ sumami wierszy i kolumn równymi $\ Displaystyle \ Lambda _ {kn}$ , a następnie $}$

${\ Displaystyle \ max _ {A \ w \ Lambda _ {kn}} \ operatorname {per} A = (k!) ^ {n/k}.}$

W ten sposób osiąga się maksimum dla macierzy o przekątnej blokowej, której bloki ukośne są macierzami kwadratowymi o rozmiarze jedynek. ${\ displaystyle k}$ . Odpowiednie stwierdzenie $dla$ przypadku, że $dzielnikiem$ jest otwartym problemem matematycznym.

Zobacz też

• Obliczanie stałej

Linki zewnętrzne

• Robina Whitty'ego. „Twierdzenie Bregmana” (PDF; 274 KB) . Twierdzenie dnia . Źródło 19 października 2015 r .