Module also offered within study programmes:
General information:
Annual:
2017/2018
Code:
AMA-2-051-MZ-s
Name:
Algebraic Methods in Combinatorics and Graph Theory 1
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Matematyka w zarządzaniu
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)
Academic teachers:
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
M_K001 Potrafi samodzielnie odszukać w literaturze, na ogół angielskojęzycznej, współczesne twierdzenia z zakresu kombinatoryki i teorii grafów. MA2A_W06, MA2A_K06 Activity during classes,
Oral answer,
Scientific paper
Skills
M_U001 Potrafi sformułować problemy i twierdzenia kombinatoryki ekstremalnej. MA2A_U10, MA2A_U01, MA2A_U17, MA2A_U02 Activity during classes,
Oral answer,
Scientific paper
M_U002 Umie przedstawić dowody twierdzeń kombinatoryki wykorzystując aparat algebry abstrakcyjnej i liniowej. MA2A_U03, MA2A_U10, MA2A_U01, MA2A_U04, MA2A_U13 Activity during classes,
Oral answer,
Scientific paper
Knowledge
M_W001 Posiada wiedzę na temat podstawowych twierdzeń współczesnej kombinatoryki. MA2A_W03, MA2A_W01, MA2A_W06 Scientific paper,
Activity during classes,
Oral answer
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
Others
E-learning
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. - - - - - + - - - - -
Module content
Seminar classes:

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.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 60 h
Module ECTS credits 2 ECTS
Participation in seminar classes 30 h
Preparation for classes 28 h
Contact hours 2 h
Additional information
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.

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).