Serwisy internetowe Uniwersytetu Warszawskiego Nie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wstęp do Kombinatoryki

Informacje ogólne

Kod przedmiotu: 1000-1M19WDK Kod Erasmus / ISCED: 11.1 / (0541) Matematyka
Nazwa przedmiotu: Wstęp do Kombinatoryki
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla matematyki 2 stopnia
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
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 2021/22" (w trakcie)

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład monograficzny, 30 godzin więcej informacji
Koordynatorzy: Piotr Nayar
Prowadzący grup: Wojciech Nadara, Piotr Nayar
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.