Module also offered within study programmes:
General information:
Name:
Algebraic Methods in Combinatorics and Graph Theory 1
Course of study:
2019/2020
Code:
AMAT-2-030-MU-s
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Insurance Mathematics
Field of study:
Mathematics
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
prof. zw. dr hab. Wojda Adam Paweł (wojda@agh.edu.pl)
Module summary

Seminarium częściowo zapewnia studentowi udział w badaniach.
Seminarium jest wybierane zgodnie z zainteresowaniami, rozszerza wiedzę teoretyczną lub zastosowania, zapoznaje z fachową literaturą.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence: is able to
M_K001 Potrafi samodzielnie odszukać w literaturze, na ogół angielskojęzycznej, współczesne twierdzenia z zakresu kombinatoryki i teorii grafów. MAT2A_K06, MAT2A_W06 Activity during classes,
Oral answer,
Scientific paper
Skills: he can
M_U001 Potrafi sformułować problemy i twierdzenia kombinatoryki ekstremalnej. MAT2A_U10, MAT2A_U17, MAT2A_U02, MAT2A_U01 Activity during classes,
Oral answer,
Scientific paper
M_U002 Umie przedstawić dowody twierdzeń kombinatoryki wykorzystując aparat algebry abstrakcyjnej i liniowej. MAT2A_U03, MAT2A_U10, MAT2A_U04, MAT2A_U01, MAT2A_U13 Activity during classes,
Oral answer,
Scientific paper
Knowledge: he knows and understands
M_W001 Posiada wiedzę na temat podstawowych twierdzeń współczesnej kombinatoryki. MAT2A_W06, MAT2A_W01, MAT2A_W03 Scientific paper,
Activity during classes,
Oral answer
Number of hours for each form of classes:
Sum (hours)
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
30 0 0 0 0 0 30 0 0 0 0 0
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Social competence
M_K001 Potrafi samodzielnie odszukać w literaturze, na ogół angielskojęzycznej, współczesne twierdzenia z zakresu kombinatoryki i teorii grafów. - - - - - + - - - - -
Skills
M_U001 Potrafi sformułować problemy i twierdzenia kombinatoryki ekstremalnej. - - - - - + - - - - -
M_U002 Umie przedstawić dowody twierdzeń kombinatoryki wykorzystując aparat algebry abstrakcyjnej i liniowej. - - - - - + - - - - -
Knowledge
M_W001 Posiada wiedzę na temat podstawowych twierdzeń współczesnej kombinatoryki. - - - - - + - - - - -
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 60 h
Module ECTS credits 2 ECTS
Udział w zajęciach dydaktycznych/praktyka 30 h
Preparation for classes 28 h
Contact hours 2 h
Module content
Seminar classes (30h):

1. Metoda wymiaru przestrzeni wektorowej.
Maksymalna liczność pewnych rodzin podzbiorów (problem miast: Parzystego i Nieparzystego oraz zagadnienia pokrewne).
2. Nierówność Fishera. Twierdzenie Nagy’a. Maksymalna liczność zbioru punktów jednakowo odległych (w przestrzeni n-wymiarowej) oraz takiego, w którym odległości przyjmują jedną z dwóch wartości.
3. Metoda elementów w pozycji ogólnej.
Podstawy algebraiczne.
4. Twierdzenie Helly’ego. Grafy Borsuka i Knesera.
5. Rodziny zbiorów z ograniczeniami dla przecięć.
Twierdzenia Erdosa-Ko-Rado.
6. Twierdzenie Erdosa-Rado o słonecznikach.
7. Twierdzenie Erdosa-Hajnala-Moona, Bollobasa.

Additional information
Teaching methods and techniques:
  • Seminar classes: Na zajęciach seminaryjnych podstawą jest prezentacja multimedialna oraz ustna prowadzona przez studentów. Kolejnym ważnym elementem kształcenia są odpowiedzi na powstałe pytania, a także dyskusja studentów nad prezentowanymi treściami.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Participation rules in classes:
  • Seminar classes:
    – Attendance is mandatory: Yes
    – Participation rules in classes: Studenci prezentują na forum grupy temat wskazany przez prowadzącego oraz uczestniczą w dyskusji nad tym tematem. Ocenie podlega zarówno wartość merytoryczna prezentacji, jak i tzw. kompetencje miękkie.
Method of calculating the final grade:

Każdy referat uczestnika seminarium jest oceniany. Ostateczna ocena jest średnią otrzymanych ocen z poszczególnych referatów. Obecność na seminariach jest obowiązkowa.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Student powinien zgłosić się do prowadzącego w celu ustalenia indywidualnego sposobu nadrobienia zaległości.

Prerequisites and additional requirements:

Brak wymagań wstępnych i dodatkowych.

Recommended literature and teaching resources:

1. Babai L. & Frankl P., Linear Algebra Methods in Combinatorics, Department of Computer Science, The University of Chicago, Preliminary version 2, 1992.
2. Diestel R., Graph Theory, Springer 2005.
3. C.D. Godsil, Algebraic Combinatorics, Chapman & Hall, 1993.
4. Jukna St., Extremal Combinatorics, Springer 2011.

Scientific publications of module course instructors related to the topic of the module:

1. A. P. Wojda; Elementy programowania liniowego i metod sieciowych, Wydawnictwa AGH, 2015.

2. Gosselin, Shonda; Szymański, Artur; Wojda, Adam Pawel
Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs;
Discrete Math. Theor. Comput. Sci. 15, No. 2, 215-222, electronic only (2013).

3. Fouquet, J.L.; Thuillier, H.; Vanherpe, J.M.; Wojda, A.P.; On isomorphic linear partitions in cubic graphs; Discrete Mathematics ; 2009, vol. 309.

4. Fouquet, Jean-Luc; Thuillier, Henri; Vanherpe, Jean-Marie; Wojda, Adam Paweł
On (K q ,k) stable graphs with small k.
Electron. J. Comb. 19, No. 2, Research Paper P50, 10 p., electronic only (2012).

5. Fouquet, J.-L.; Thuillier, H.; Vanherpe, J.-M.; Wojda, A.P.
On (K q ,k) vertex stable graphs with minimum size.
Discrete Math. 312, No. 14, 2109-2118 (2012).

6. Szymanski, Artur; Wojda, A.Paweł
Cyclic partitions of complete uniform hypergraphs. (English) Zbl 1204.05066
Electron. J. Comb. 17, No. 1, Research Paper R118, 12 p., electronic only (2010).

7. Adamus, Lech; Orchel, Beata; Szymański, Artur; Wojda, A.Paweł; Zwonek, Małgorzata
A note on t-complementing permutations for graphs.
Inf. Process. Lett. 110, No. 2, 44-45 (2009).

8. Szymański, Artur; Wojda, Adam Paweł
Self-complementing permutations of k-uniform hypergraphs;
Discrete Math. Theor. Comput. Sci. 11, No. 1, 117-124, electronic only (2009).

Additional information:

Podczas semestru każdy uczestnik seminarium referuje co najmniej dwukrotnie.
Około 50% czasu zajęć poświęcone jest przypomnieniu bądź uzupełnieniu wiadomości z zakresu algebry i algebry liniowej, niezbędnych dla zrozumienia zajęć, które w dużej mierze stanowią zastosowania tych wiadomości i umiejętności w kombinatoryce i teorii grafów.
Biorący udział w seminarium studenci ostatniego roku studiów referują pod koniec semestru stan zaawansowania przygotowywanej pracy magisterskiej (na referat ten zapraszany(a) jest promotor(ka) rozprawy).