Wstęp do Kombinatoryki
Informacje ogólne
Kod przedmiotu: | 1000-1M19WDK |
Kod Erasmus / ISCED: |
11.1
|
Nazwa przedmiotu: | Wstęp do Kombinatoryki |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty monograficzne dla matematyki 2 stopnia Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | (brak danych) |
Rodzaj przedmiotu: | monograficzne |
Założenia (opisowo): | zakłada się, że student zna podstawy algebry liniowej (Geometria z Algebrą Liniową I) oraz analizy matematycznej (Analiza Matematyczna I.1) |
Skrócony opis: |
Wykład poświęcony będzie kilku podstawowym tematom rozważanym w kombinatoryce. W szczególności zostaną omówione następujące tematy: zliczanie, kombinatoryka punktów i zbiorów w R^n, kombinatoryka ekstremalna, metoda probabilistyczna i jej zastosowania w teorii grafów i teorii liczb, elementy teorii grafów, metoda algebraiczna, analiza na kostce dyskretnej. Będziemy podkreślać związki kombinatoryki z innymi działami matematyki. W szczególności zobaczymy, jak rachunek prawdopodobieństwa, metody analityczne i metody algebraiczne mogą posłużyć jako narzędzia do badania obiektów kombinatorycznych. |
Pełny opis: |
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) |
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. |
Efekty uczenia się: |
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. |
Metody i 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. |
Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN CW
WT ŚR CW
CZ WYK-MON
PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład monograficzny, 30 godzin
|
|
Koordynatorzy: | Piotr Nayar | |
Prowadzący grup: | Łukasz Bożyk, Jacek Jakimiuk, Piotr Nayar | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr letni 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2025-02-17 - 2025-06-08 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład monograficzny, 30 godzin
|
|
Koordynatorzy: | Piotr Nayar | |
Prowadzący grup: | (brak danych) | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.