Czułość funkcji logicznych (II)

W pierwszej części artykułu (Delta 7/2020) omówiliśmy pojęcia funkcji logicznej, jej czułości i przedstawiliśmy, na razie bez dowodów, pewne związane z nimi twierdzenia, udowodnione w pracy [1]. Celem drugiej części jest przedstawienie owych dowodów w wersji nieco uproszczonej w stosunku do oryginalnej pracy [1], ale wciąż wymagającej znajomości podstaw algebry liniowej, w tym mnożenia macierzy i pewnej wiedzy o wymiarze przestrzeni liniowej.

Q12 — Na przykład w $Q 12$ połączone będą między innymi
$|x 859 001101011011 2$ i
$|y 843 001101001011 2$

Niech $n$ będzie dowolną dodatnią liczbą całkowitą i niech $=2n. N$ Zapiszmy elementy zbioru $−1} |Vn = {0,1,...,N$ w układzie dwójkowym (uzupełniając w miarę potrzeby nieznaczącymi początkowymi zerami, tak by każda liczba miała dokładnie $n$ cyfr) i przedstawmy je graficznie w ten sposób, że elementy $Vn$ (zwane wierzchołkami) będą punktami, a odcinki (zwane krawędziami) połączą pary wierzchołków różniące się w układzie dwójkowym tylko jedną cyfrą. Uzyskany graf nazwiemy n-wymiarową kostką $nQ$ (nazwa wiąże się niewątpliwie z podobieństwem $3 |Q$ do szkieletu sześcianu, czyli standardowej kostki do gry). Spróbujmy przezwyciężyć fakt, że bezpośrednio odczuwamy istnienie tylko trzech wymiarów, spoglądając na kostki rekurencyjnie: $| 1 Q$ to dwa punkty połączone odcinkiem, $| 2 Q$ to dwa odcinki, np. dolny i górny, połączone dwiema pionowymi krawędziami, $3 |Q$ to dwie kopie $2, Q$ np. dolny i górny kwadrat, połączone czterema pionowymi krawędziami, $|...$ , $m+1 Q$ to dwie kopie $m, |Q$ połączone $|2m$ krawędziami i tak dalej.

Zapowiedziane pod koniec pierwszej części twierdzenie (jeśli ponad połowę wierzchołków $| n$ -wymiarowej kostki zajmują mrówki, to któraś z nich ma co najmniej $√ -- | n$ sąsiadek) możemy sformułować w następujący równoważny sposób.

Twierdzenie (Huang). Jeśli wyróżnimy niektóre wierzchołki $|n$ -wymiarowej kostki $n, Q$ czyli wybierzemy podzbiór $W⊆ Vn,$ przy zachowaniu warunku, że każdy element $W$ ma mieć mniej niż $-- √ n$ sąsiadów należących do $W,$ to wyróżnione wierzchołki stanowić będą co najwyżej połowę wszystkich wierzchołków kostki, czyli $/2. W ⩽ N$

W terminologii teorii grafów twierdzenie Huanga brzmi:

Twierdzenie. każdy indukowany podgraf $⊆Qn |G$ spełnia $√ )<n V(G) ⩽2n−1.∆(G$

Dużo krócej, ale trzeba wpierw wyjaśnić, że $) V (G$ to zbiór wierzchołków grafu $,∆(G) G$ to największy stopień wierzchołka (stopień to z kolei liczba krawędzi o końcu w danym wierzchołku), a podgraf indukowany oznacza pewne wierzchołki wraz ze wszystkimi łączącymi je krawędziami $n.Q$

Cały artykuł dostępny jest w wersji do druku: (533 KB)