Twierdzenie Becka-Fiala

W matematyce twierdzenie Becka-Fiali jest głównym twierdzeniem w teorii rozbieżności dzięki Józsefowi Beckowi i Tiborowi Fiali. Rozbieżność dotyczy kolorowania elementów zestawu podstawowego w taki sposób, aby każdy zestaw w pewnym systemie zestawu był jak najbardziej zrównoważony, tj. zawierał w przybliżeniu taką samą liczbę elementów każdego koloru. Twierdzenie Becka – Fiali dotyczy przypadku, w którym każdy element nie pojawia się wiele razy we wszystkich zbiorach. Twierdzenie gwarantuje, że jeśli każdy element pojawi się co najwyżej t razy, to elementy te można pokolorować tak, aby nierównowaga wynosiła co najwyżej 2 t − 1 .

Oświadczenie

Formalnie, biorąc pod uwagę wszechświat

${\ Displaystyle [n] = \ {1, \ ldots, n \}}$

i zbiór podzbiorów

${\ Displaystyle S_ {1}, S_ {2}, \ ldots, S_ {m} \ subseteq [n]}$

tak, że dla każdego ja $\ Displaystyle i \ in [n]}$

${\ Displaystyle \ vert \ {j: i \ w S_ {j} \} \ vert \ równoważnik t,}$

wtedy można znaleźć zadanie

${\ Displaystyle x: [n] \ strzałka w prawo \ {-1, + 1 \}}$

takie że

${\ Displaystyle | x (S_ {j}) | \ równoważnik 2t-1, \ forall j {\ tekst {gdzie}} x (S_ {j}): = \ suma _ {i \ w S_ {j}} x_ {I}.}$

Szkic dowodowy

Dowód opiera się na prostym argumencie liniowo-algebraicznym. Zacznij od ${\ displaystyle x_ {i} = 0}$ dla wszystkich elementów i wywołaj wszystkie zmienne jako aktywne na początku.

Rozważ tylko zestawy z ${\ Displaystyle \ vert S_ {j} \ vert > t}$ . Ponieważ każdy element pojawia się najwyżej razy w zestawie, takich zestawów jest mniej niż $n} .$$displaystyle$ Teraz wymuś dla nich ograniczenia liniowe ${\ Displaystyle \ suma _ {i \ in S_ {j}} x_ {i} = 0} .$$Ponieważ jest$ nietrywialna podprzestrzeń liniowa z mniejszą liczbą ograniczeń niż zmiennych, niezerowe rozwiązanie. $Normalizuj$ z wartości Ustaw tę wartość i dezaktywuj tę zmienną. Teraz zignoruj ​​​​zestawy z mniej niż $zmiennymi$ . I powtórz tę samą procedurę, wymuszając liniowe ograniczenia, aby suma aktywnych zmiennych każdego pozostałego zestawu była wciąż taka sama. Na podstawie tego samego argumentu zliczania istnieje nietrywialne rozwiązanie, więc można przyjmować liniowe kombinacje tego z pierwotnym, aż jakiś element stanie się ${\ Displaystyle + 1, -1}$ . Powtarzaj, aż wszystkie zmienne zostaną ustawione.

$nieustawione$ suma wartości jego zmiennych wynosi zero i są co najwyżej zmienne. Zmiana w nich może wzrosnąć ${\ Displaystyle | x (S_ {j})|}$ najwyżej do ${\ Displaystyle 2t-1}$ .

• József Beck i Tibor Fiala (1981). „ Twierdzenia o tworzeniu liczb całkowitych” . Dyskretna matematyka stosowana . 3 (1): 1–8. doi : 10.1016/0166-218X(81)90022-6 .
•   Chazelle, Bernard (2000). Metoda rozbieżności: losowość i złożoność . Nowy Jork: Cambridge University Press. ISBN 0-521-77093-9 .