Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Hipergrafy i konfiguracje
Tok studiów:
2016/2017
Kod:
AMA-3-202-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia III stopnia
Specjalność:
-
Kierunek:
Matematyka
Semestr:
2
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr hab. Meszka Mariusz (meszka@agh.edu.pl)
Osoby prowadzące:
dr hab. Meszka Mariusz (meszka@agh.edu.pl)
dr hab. Żak Andrzej (zakandrz@agh.edu.pl)
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Posiada poszerzoną, podbudowaną teoretycznie wiedzę ogólną związaną z teorią hipergrafów oraz konfiguracji kombinatorycznych. Student demonstrates a deeper general knowledge in the theory of hypergraphs and combinatorial designs. MA3A_W01 Egzamin
Umiejętności
M_U001 Posiada umiejętność definiowania i rozwiązywania różnorodnych zadań w teorii hipergafów oraz konfiguracji kombinatorycznych. Student knows how to formulate and solve various problems in the theory of hypergraphs and combinatorial designs. MA3A_U01 Egzamin,
Aktywność na zajęciach
M_U002 Ma umiejętność pozyskiwania aktualnych informacji naukowych w tej dyscyplinie. Student knows how to get the most actual information in this topic. MA3A_U01 Udział w dyskusji
Kompetencje społeczne
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy lub rozumowań, zdaje sobie sprawę z potrzeby dalszego kształcenia. Student is aware of his/her level of knowledge in the topic; he/she realises the need of constant learning. MA3A_K01 Egzamin,
Aktywność na zajęciach
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Posiada poszerzoną, podbudowaną teoretycznie wiedzę ogólną związaną z teorią hipergrafów oraz konfiguracji kombinatorycznych. Student demonstrates a deeper general knowledge in the theory of hypergraphs and combinatorial designs. + + - - - - - - - - -
Umiejętności
M_U001 Posiada umiejętność definiowania i rozwiązywania różnorodnych zadań w teorii hipergafów oraz konfiguracji kombinatorycznych. Student knows how to formulate and solve various problems in the theory of hypergraphs and combinatorial designs. + + - - - - - - - - -
M_U002 Ma umiejętność pozyskiwania aktualnych informacji naukowych w tej dyscyplinie. Student knows how to get the most actual information in this topic. + + - - - - - - - - -
Kompetencje społeczne
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy lub rozumowań, zdaje sobie sprawę z potrzeby dalszego kształcenia. Student is aware of his/her level of knowledge in the topic; he/she realises the need of constant learning. + + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

PL

1. Podstawowe pojęcia i fakty
Definicje; przykłady; podstawowe pojęcia; podstawowe zależności.

2. Rodziny przecinające
Twierdzenie Erdősa-Ko-Rado; twierdzenie Bollobása; twierdzenie Spernera; problem Littlewooda-Offorda.

3. Transwersale
Definicja transwersali; liczebności transwersali minimalnych – współczynniki τ i τ’; twierdzenie Erdősa-Hajnala o mocy transwersali dla 3-jednolitych hipergrafów liniowych.

4. Skojarzenia
Definicja skojarzenia; przykłady; własność Königa; twierdzenie Seymoura o mocy skojarzenia w hipergrafie liniowym.

5. Problemy hamiltonowskie 1
Definicja l-cyklu w hipergrafie k-jednolitym; warunki typu Diraca;

6. Problemy hamiltonowskie 2
Liczba Turána dla l-cyklu Hamiltona; twierdzenie Tuzy; twierdzenie Glebova, Persona i Weps;

7. Problemy hamiltonowskie 3
Liczba nasycająca dla l-cyklu Hamiltona; ograniczenie dolne; konstrukcje hipergrafów minimalnych (z dowodem dla przypadku l = 1).

8. Systemy trójek Steinera
Warunki konieczne i wystarczające; podstawowe metody konstrukcji.

9. Konfiguarcje BIBD
Przykłady; warunki konieczne istenienia; nierówność Fischera; podstawowe metody konstrukcji.

10. Konfiguracje rozkładalne
Systemy trójek Kirkmana – istnienie oraz konstrukcje; inne konfiguracje rozkładalne.

11. Konfiguracje PBD, GDD oraz TD
Przykłady; istnienie; podstawowe metody konstrukcji.

12. Kwadraty i prostokąty łacińskie
Istnienie; zanurzanie; związek z innymi konfiguracjami; quasigrupy.

13. Płaszczyzny afiniczne i rzutowe
Istnienie oraz konstrukcje.

14. Inne rodziny konfiguracji
t-konfiguracje; systemy cykli; konfiguracje skierowane.

EN

1. Basic facts and notions
Definitions; examples; basic notions; basic facts.

2. Intersecting families
The Erdős-Ko-Rado theorem; Bollobás theorem; Sperner’s theorem; The Littlewood-Offord problem.

3. Transversal sets
Definition of a transversal set; cardinalities of minimal transversal sets – the coefficients τ and τ’; the Erdős-Hajnal theorem on a cardinality of a transversal set in a 3-uniform linear hypergraph.

4. Matchings
Definition of a matching; examples; the König property; the Seymour theorem on a cardinality of a matching in a linear hypergraph.

5. Hamiltonian problems 1
Definition of an l-cycle in a k-uniform hypergraph; Dirac-type conditions;

6. Hamiltonian problems 2
Turán number for a hamiltonian l-cycle; Tuza’s theorem; Glebov-Person-Weps theorem;

7. Hamiltonian problems 3
Saturation number for a hamiltonian l-cycle; lower bound; constructions of minimal hypergraphs (with a proof in the loose case).

8. Steiner triple systems
Necessary and sufficent conditions for the existence; basic constructions.

9. Balanced incomplete block designs (BIBD)
Examples, necessary conditions; Fischer’s inequality; basic constructions.

10. Resolvable designs
Kirkman trilpe systems – existence and constructions; other resolvable designs.

11. Pairwise balanced designs (PBD), group divisible designs (GDD) and transversal designs (TD)
Examples; existence; basic constructions.

12. Latin squares and rectangles
Existence; embedding; connection to other designs; quasigroups.

13. Affine and projective planes
Existence and constructions

14. Other designs
t-designs; cycle systems; directed designs.

Ćwiczenia audytoryjne:
Program ćwiczeń zgodny z wykładami
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 102 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 28 godz
Udział w ćwiczeniach audytoryjnych 28 godz
Samodzielne studiowanie tematyki zajęć 30 godz
Egzamin lub kolokwium zaliczeniowe 1 godz
Samodzielne studiowanie tematyki zajęć 15 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena z egzaminu.

Grade from examination.

Wymagania wstępne i dodatkowe:

Podstawy kombinatoryki ze szczególnym uwzględnieniem teorii grafów.

Basic knowledge in combinatorics, mostly in graph theory.

Zalecana literatura i pomoce naukowe:

1 C.C. Lindner, C.A. Rodger, Design Theory, Second Edition, Chapman & Hall/CRC, 2009.

2 D.R. Stinson, Combinatorial Designs, Constructions and Analysis, Springer, 2004.

3 W.D. Wallis, Introduction to Combinatorial Designs, Chapman & Hall/CRC, 2007.

4 C.J. Colbourn, A. Rosa, Tr[iple Systems, Clarendon Press, 1999.

5 C.J. Colbourn, J.H. Dinitz (eds.), Handbook of Combinatorial Designs, Second Edition, Chapman & Hall/CRC, 2006.

6 C. Berge, Hypergraphs: The Theory of Finite Ses, Amsterdam, Netherlands: North-Holland, 1989.

7 A. Gyárfás, Advanced Combinatorics Handouts, manuskrypt.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Meszka, Mariusz; Rosa, Alexander; Cubic leaves, Australas. J. Comb. 61, 114-129, electronic only (2015).

2. Lindner, Charles C.; Meszka, Mariusz; Rosa, Alexander ; From squashed 6-cycles to Steiner triple systems, J. Comb. Des. 22, No. 5, 189-195 (2014).

3. Horňák, Mirko; Kalinowski, Rafał; Meszka, Mariusz; Woźniak, Mariusz;
Minimum number of palettes in edge colorings.
Graphs Comb. 30, No. 3, 619-626 (2014).

4. Meszka, Mariusz, The chromatic index of projective triple systems; J. Comb. Des. 21, No. 11, 531-540 (2013).

5. Cichacz, Sylwia; Froncek, Dalibor; Meszka, Mariusz; Decomposition of complete graphs into small generalized prisms; AKCE Int. J. Graphs Comb. 10, No. 3, 285-293 (2013).

6. Lindner, C.C.; Meszka, M.; Rosa, A.; Triple metamorphosis of twofold triple systems; Discrete Math. 313, No. 19, 1872-1883 (2013).

7. Żak, Andrzej; General lower bound on the size of (H;k)-stable graphs; J. Comb. Optim. 29, No. 2, 367-372 (2015).

8. Żak, Andrzej; On packing two graphs with bounded sum of sizes and maximum degree;
SIAM J. Discrete Math. 28, No. 4, 1686-1698 (2014).

9. Żak, Andrzej; A generalization of an independent set with application to (K q ;k)-stable graphs; Discrete Appl. Math. 162, Part 1, 421-427 (2014).

10. Żak, Andrzej; On embedding graphs with bounded sum of size and maximum degree; Discrete Math. 329, 12-18 (2014).

11. Żak, Andrzej; On (K q ;k)-stable graphs; J. Graph Theory 74, No. 2, 216-221 (2013).

12. Zak, Andrzej; Near packings of graphs; Electron. J. Comb. 20, No. 2, Research Paper P36, 8 p., electronic only (2013).

13. Ruciński, Andrzej; Ẓak, Andrzej; Hamilton saturated hypergraphs of essentially minimum size; Electron. J. Comb. 20, No. 2, Research Paper P25, 16 p., electronic only (2013).

14. Żak, Andrzej; Growth order for the size of smallest Hamiltonian chain saturated uniform hypergraphs;
Eur. J. Comb. 34, No. 4, 724-735 (2013).

Informacje dodatkowe:

Brak