Wstęp do Kombinatoryki 1000-1M19WDK
Planujemy omówić następujące tematy:
I. Zliczanie: funkcje tworzące i rekurencje liniowe, liczby Fibonacciego, Bella i Stirlinga oraz ich własnośći, struktury Catalana (triangulacje wielokątów, ścieżki Dyck'a, partycje bez przecięć, permutacje bez wzoru 123), zasad odbicia, lemat Burnside, tableau Younga, formuła haczykowa.
II. Kombinatoryka geometryczna: twierdzenia Helly'ego, Radona i Carathéodory'ego, problem dwóch dystansów, kontrprzykad Kahna i Kalaia na hipotezę Borsuka, krzywa potęgowa i wielościany cykliczne, twierdzenie Szemerédiego–Trottera, rozwiązania Banga problemu deskowego Tarskiego, równokątne linie w R^n, nierówność Welcha.
III. Kombinatoryka ekstremalna: twierdzenie Erdősa-Ko-Rado, twierdzenie Spernera i nierówność LYM, twierdzenia Dilwortha and Mirsky'ego, problem Littlewooda–Offorda, lemat Sauera–Shelaha i wymiar Vapnika–Chervonenkisa, nierównośc Fishera, liczby Ramseya, twierdzenie Erdősa–Szekeresa.
IV. Metoda probabilistyczna: metoda pierwszego i drugiego momentu wraz z zastosowaniami, lemat lokalny Lovasza, graf losowy Erdősa-Renyi oraz przykłady zjawiska "ostrego przejścia".
V. Elementy teorii grafów: grafy Eulera i Hamiltona, grafy planarne, wzór Eulera, formuła Cayleya, liczba chromatyczna grafu, twierdzenie o pięciu barwach, grafy skierowane, turnieje, twierdzenie Mengera, twierdzenie Halla, twierdzenie max-flow min-cut, elementy spektralnej teorii grafów, twierdzenie macierzowe Kirchhoffa, ekspandery i ich podstawowe własnośći, matroidy (podstawy).
VI. Metody algebraiczne w kombinatoryce: Combinatorial Nullstellensatz, nieróność Cauchy'ego-Davenporta, twierdzenie Erdősa-Ginzburga-Ziva, dowód hipotezy Kakeyi w ciałach skończonych, twierdzenie Grahama-Pollaka.
VII. Funkcje boolowskie i kostka dyskretna: układ Walsha i analiza spektralna na kostce dyskretnej, twierdzenie Condorceta z teorii wyboru społecznego, nierówność izoperymetryczna Harpera, nierówność Chinczyna, dowód Huanga "sensitivity conjecture", hiperkontrakcja i twierdzenie Kahna–Kalaia–Liniala.
VIII. Pozostałe tematy: ciąg Thuego bez powtórzeń, metody topologiczne w kombinatoryce (dowód hipotezy Knesera), elementy kombinatoryki addytywnej (dowód twierdzenia Rotha o postępach arytmetycznych długości 3), singularność macierzy Bernoulliego, hipoteza Komlosa, nierówność Brunna-Minkowskiego i nierówność izoperymetryczna, elementy kryptografii (test Millera-Rabina, algorytm RSA)
Rodzaj przedmiotu
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
Student:
1. Umie stosować podstawowe techninki zliczania.
2. Zna podstawowe kombinatoryczne własności zbiorów wypukłych w R^n.
3. Jest zaznajomiony z kombinatoryką skończonych podzbiorów R^n (np. z problemami związanymi z odległościami i iloczynami skalarnymi).
4. Zna podstawowe twierdzenia kombinatoryki ekstremalnej.
5. Umie stosować metodę probabilistyczną.
6. Zna podstawy teorii grafów.
7. Zna przykłady zastosowania metody algebraicznej w kombinatoryce.
8. Jest zaznajomiony z analizą na kostce dyskretnej.
9. Zna podstawowe przykłady twierdzeń kombinatoryki addytywnej.
Kryteria oceniania
ocena będzie wypadkową ocen z prac domowych, dwóch kolokwiów, egzaminu pisemnego oraz z egzaminu ustnego (dla wybranych osób). Kryteria oceny będą różne dla studentów różnych etapów studiów.
Literatura
1. N. Alon, J. H. Spencer, The probabilistic method (2ed), New York: Wiley-Interscience, 2000.
2. R. O'Donnell, Analysis of Boolean functions, Cambridge University Press, New York, 2014.
3. J. Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, 212. Springer-Verlag, New York, 2002.
4. N. Alon, Combinatorial nullstellensatz, Combinatorics, Probability and Computing 8, 1999.
5. T. Tao, V. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., vol. 105, Cambridge Univ. Press, Cambridge, 2006.
6. I. Pak, Lectures on Discrete and Polyhedral Geometry, https://www.math.ucla.edu/~pak/book.htm
7. B. Bollobás, Set systems, hypergraphs, families of vectors and combinatorial probability, Cambridge University Press, Cambridge, 1986.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: