Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Wstęp do Kombinatoryki

Informacje ogólne

Kod przedmiotu: 1000-1M19WDK
Kod Erasmus / ISCED: 11.1 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Matematyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

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 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-01-28
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład monograficzny, 30 godzin więcej informacji
Koordynatorzy: Piotr Nayar
Prowadzący grup: Łukasz Bożyk, Jacek Jakimiuk, 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.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)