Kombinatoryka ekstremalna i przesuwanie zbiorów

Najogólniej mówiąc, kombinatoryka ekstremalna zajmuje się pytaniami o to, jaki jest rozmiar największego (lub najmniejszego) możliwego zbioru obiektów danego typu, spełniającego pewien zadany warunek i jak takie ekstremalne przypadki wyglądają.

Wiele z nich dotyczy rodzin zbiorów, jak np.

Pytanie 1. Jaka jest największa rodzina podzbiorów zbioru $|{1,2,...,n},$ której każde dwa elementy mają niepuste przecięcie?

Rodzinę spełniającą ten warunek nazywać będziemy przecinającą się. Oznaczmy dla wygody

[n] = {1,2,...,n}.

Nietrudno wskazać przykład sporej rodziny przecinającej się: dla dowolnego $|a∈ [n]$ spełnia ten warunek rodzina wszystkich podzbiorów $[n],$ które zawierają $a,$ składająca się z $2n−1$ zbiorów.

Więcej już nie uzyskamy, o czym przekonamy się, ustawiając wszystkie podzbiory zbioru $|[n]$ w $|2n−1$ par postaci ${A,[n] ∖ A}.$ Dowolna rodzina przecinającą się zawiera co najwyżej jeden zbiór z każdej pary, więc jej liczność nie przekracza $n−1 |2 ,$ co chcieliśmy wykazać.

Po tej udanej rozgrzewce rozważmy podobny problem dla rodzin $|r$ -jednorodnych, tzn. składających się tylko ze zbiorów ustalonej mocy $|r∈ [n].$

Pytanie 2. Jaka jest największa $r$ -jednorodna, przecinającą się rodzina podzbiorów zbioru $|[n]?$

Modyfikując wcześniejszy przykład, możemy wskazać $|(r,n)$ -rodzinę wszystkich $r$ -elementowych podzbiorów $[n]$ zawierających pewną ustaloną liczbę $a ∈ [n]$ ; rodzina ta liczyć będzie $n−1 (r−1)$ elementów.

Podobnie jak wcześniej, więcej się nie da, ale dowód maksymalności jest teraz bardziej wymagający. My skorzystamy z ciekawej i bardzo użytecznej techniki przesuwania (ang. shifting) rodziny zbiorów, która ograniczy nasz problem do dość wygodnych rodzin.

O co chodzi w przesuwaniu? Zakładamy, że dana jest pewna rodzina $|ℱ$ podzbiorów $|[n].$ Dla dowolnej pary liczb $1⩽ i < j⩽ n$ określamy operację $si j$ na zbiorach $|A$ jako "podmianę" liczby $j$ na $|i,$ o ile jest to możliwe i o ile prowadzi do powstania zbioru spoza $ℱ.$ Bardziej precyzyjnie

s (A) i j

Widać, że definicja $|s (A) i j$ zależy nie tylko od $A, |$ ale też od rodziny $|ℱ,$ którą rozważamy, więc lepiej byłoby pisać $ℱ si j(A)$ zamiast $sij(A), |$ ale na szczęście i tak nie napotkamy na kłopoty w oznaczeniach. Stosując ją, zastępujemy pewne wystąpienia liczby $| j$ w zbiorach rodziny $|ℱ$ wystąpieniami mniejszej liczby $i,$ nie zmieniając mocy modyfikowanych zbiorów. Sprawdzając kilka prostych przypadków, można też zauważyć, że operacja $si j$ jest różnowartościowa na $|ℱ,$ a zatem wynik jej zastosowania do wszystkich zbiorów rodziny, tzn. rodzina $|s (ℱ) = {s (A) i j i j$ liczy sobie tyle samo elementów co $ℱ.$ Nazwijmy wagą zbioru $A$ sumę jego elementów, zaś wagą rodziny $ℱ$ - sumę wag zbiorów należących do $ℱ.$ Zauważmy, że waga $si j(ℱ)$ jest nie większa od wagi $ℱ,$ a równość zachodzi wtedy i tylko wtedy, gdy $|s (A) i j$ dla każdego $A$ Najciekawsze jednak jest to, że jeśli $|ℱ$ jest rodziną przecinającą się, to jest nią również $si j(ℱ).$ Ponieważ jednak niniejszy artykuł i tak jest bogato udekorowany matematycznymi formułami, techniczny (acz nietrudny) dowód tego faktu pozostawiam Czytelnikowi Dociekliwemu jako ćwiczenie.

Potrzebne nam będzie jeszcze jedno pojęcie - rodzinę $ℱ$ nazwiemy przesuniętą, jeżeli dla każdych $1⩽ i < j⩽ n$ zachodzi $s (ℱ) = ℱ, i j$ co oznacza tak naprawdę, że $si j(A)$ dla każdego $A$ bo rodziny $|ℱ$ i $si j(ℱ)$ mają taką samą wagę. Równoważnie, rodzina $ℱ$ jest przesunięta, jeśli dla każdych liczb $1⩽ i < j⩽ n$ oraz każdego zbioru $|A$ z warunków $j ∈A,$ wynika, że $|(A$ W zbiorach z przesuniętej rodziny $ℱ$ można podmieniać większe liczby na mniejsze, otrzymując dalej zbiory z $ℱ.$

Rozważmy teraz dowolną rodzinę $|ℱ$ i jeśli istnieją $|1⩽ i < j⩽ n$ takie, że $|si j(ℱ) ≠ℱ,$ to zastąpmy $ℱ$ przez $si j(ℱ)$ i powtarzajmy tę procedurę, dopóki jest to możliwe. Kiedyś musi się ona zakończyć z uwagi na zmniejszającą się wagę rozważanej rodziny, a zatem z każdej rodziny $ℱ$ możemy, stosując skończenie wiele operacji postaci $|si j,$ otrzymać rodzinę przesuniętą $′ ℱ .$

Możemy teraz uzasadnić odpowiedź na pytanie 2. Wykażemy przez indukcję względem $n,$ że jeśli $|1⩽ r⩽ n/2$ oraz $ℱ$ jest $|(r,n)$ -rodziną, to $n−1 | ℱ ⩽( r− 1).$

Bazę indukcji stanowi przypadek $n = 2,$ w którym sprawa jest oczywista. Przejdźmy do dowodu kroku indukcyjnego: niech $1 ⩽r ⩽ n/2$ oraz $|ℱ$ będzie $|(r,n)$ -rodziną. Jeśli $|r = 1,$ to łatwo zobaczyć, że $| ℱ ⩽1 = (n−r− 1 1).$ Jeśli zaś $r = n/2,$ to możemy powtórzyć rozumowanie użyte przy okazji pytania 1 i podzielić $r$ -elementowe podzbiory $[n]$ na pary postaci $|{A,$ Do każdej z nich należy co najwyżej jeden element rodziny $|ℱ,$ więc $ℱ ⩽ 12(nr) = (nr−−11).$

Pozostaje przypadek $|1 < r < n/2.$ Rodzinę $ℱ$ możemy operacjami $|si j$ przekształcić do rodziny $′ ℱ ,$ która jest przesunięta, a także, z uwagi na własności zachowywane przez $si j,$ jest $|(r,n)$ -rodziną i liczy tyle samo elementów, co $|ℱ.$ Sprowadziliśmy zatem problem do rodzin przesuniętych. Próbując zredukować problem do podzbiorów $|[n − 1],$ rozważmy rodziny $′ |ℱ0 = {A$ oraz $′ ℱ 1 = {A$

$|ℱ′ 0$ jest z założenia $(r,n − 1)$ -rodziną oraz $|1⩽ r⩽ (n −1)/2,$ więc na mocy założenia indukcyjnego, $′ n−2 ℱ0 ⩽ (r−1).$

Z kolei $ℱ ′ 1$ jest $(r −1)$ -jednorodną rodziną podzbiorów $[n − 1],$ a także $|1⩽ (r− 1)⩽ (n −1)/2.$ Sprawdźmy, że jest też rodziną przecinającą się, aby móc skorzystać z założenia indukcyjnego. Przypuśćmy nie wprost, że pewne $A,$ są rozłączne. Ponieważ $A$ więc istnieje $|k∈ [n −1]∖ (A$ Do przesuniętej rodziny $ℱ ′$ należą zbiory $A1$ więc należy również do niej $|(A1$ Widać teraz, że $|A$ i $B ∪ {n}$ są rozłącznymi elementami przecinającej się rodziny $ℱ′,$ czyli mamy sprzeczność. Z założenia indukcyjnego dostajemy więc $| ℱ ′ ⩽ (n−2). 1 r−2$

Podsumowując, $| ℱ = ℱ′ = ℱ0′ + ℱ′1 ⩽ (nr−−21) + (nr−−22) = (nr−− 11),$ co kończy dowód kroku indukcyjnego i rozwiązanie problemu.

Dość naturalny pomysł na krok indukcyjny mógł zadziałać dopiero po przejściu do rodziny przesuniętej. Otrzymany rezultat znany jest jako twierdzenie Erdősa-Ko-Rado, a przyjrzeliśmy się właśnie jego pierwszemu dowodowi. Na tym się jednak kariera techniki przesuwania w kombinatoryce nie skończyła. Udało się dzięki niej rozwiązać wiele problemów i wciąż jest ona z powodzeniem stosowana.