Extremal Combinatorics

Informacje ogólne

Kod przedmiotu:	1000-2M14EC
Kod Erasmus / ISCED:	11.3 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. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Extremal Combinatorics
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:	Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne:	(brak) 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:	angielski
Rodzaj przedmiotu:	monograficzne
Skrócony opis:	The purpose of this course is to provide an introduction to the branch of combinatorial theory known as extremal combinatorics. A classical problem in extremal combinatorics is of the following nature: find the minimum or maximum size of a collection of finite objects that satisfies certain conditions and, if possible, characterize structure of the extremal families. We will primarily focus on extremal problems on systems of finite sets. Alongside theorems that are the cornerstones of the theory, there will be special emphasis on major tools and techniques, particularly methods from linear algebra. We will also highlight certain applications to geometry and computer science.
Pełny opis:	1.Sperner systems: Sperner's theorem, the LYM (Lubell-Yamamoto-Meshalkin) inequality, Bollobas' ''set pairs'' theorem. 2.Intersecting set systems: the Erdős-Ko-Rado theorem, Katona's proof using cyclic permutations, Frankl's generalization, the complete intersection theorem of Ahlswede-Khachatrian. 3.Compression techniques and shadows of set systems: the Kruskal-Katona theorem, Lovasz's version, Daykin's proof of Erdős-Ko-Rado using Kruskal-Katona. 4.Sunflowers: The Sunflower Lemma of Erdős-Rado, the Sunflower Conjecture, and an algorithmic application involving the d-HITTING SET problem. 5.The linear algebra bound: the Oddtown theorem and variants, Fisher's inequality, packing complete bipartite graphs (Graham-Pollak). 6.The method of linearly independent polynomials: Covering a cube with hyperplanes, set systems with restricted intersection sizes. 7.Applications to discrete geometry: Two-distance point sets in Euclidian space, a disproof of Borsuk's conjecture using extremal set theory. 8.Exterior products: The exterior algebra of a vector space, a proof of a variant of Bollobas' ''set pairs'' theorem using exterior products. An algorithmic application of Bollobas' theorem to computing representative sets, illustrated using the k-PATH problem. 9.Traces of set systems: VC-dimension of a set system, Sauer-Shelah lemma, applications to computational learning theory. 10.The Four Functions Theorem: Statement and proof, and an application to an extremal problem on union of intersecting families.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.