Przeskocz do treści

Delta mi!

Loading

Kombinatoryka ekstremalna i przesuwanie zbiorów

Damian Orlef

o artykule ...

  • Publikacja w Delcie: kwiecień 2016
  • Publikacja elektroniczna: 30 marca 2016
  • Autor: Damian Orlef
    Afiliacja: student, Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (114 KB)

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]?

Taką rodzinę będziemy nazywać w skrócie (r,n) -rodziną. Dla |r > n/2 widać, że nawet rodzina wszystkich |r -elementowych podzbiorów zbioru |[n] jest |(r,n) -rodziną, więc w dalszym ciągu zakładamy, że |1⩽ r⩽ n/2.

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.

obrazek

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.