Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Symmetry Breaking of Discrete Structures
Tok studiów:
2019/2020
Kod:
ZSDA-3-0304-s
Wydział:
Szkoła Doktorska AGH
Poziom studiów:
Studia III stopnia
Specjalność:
-
Kierunek:
Szkoła Doktorska AGH
Semestr:
0
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Angielski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr hab, prof. AGH Kalinowski Rafał (kalinows@agh.edu.pl)
Dyscypliny:
matematyka
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

In order to understand a structure it is essential to understand its symmetries and how they change in dependence on variations of the structure. In this course this is exemplified by the study of automorphisms of finite and infinite graphs and how they can be broken by edge or vertex colorings. On the way essentials of permutation groups, Cayley graphs, elements of combinatorial group theory, set theory and random graphs are touched.

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 Student can search for information in the literature, also in foreign languages SDA3A_K02 Odpowiedź ustna
M_W002 Student has in-depth knowledge in the chosen field of theoretical or applied mathematics SDA3A_W02, SDA3A_W01
Umiejętności: potrafi
M_U001 Student speaks English at intermediate level (B2) at a level sufficient for reading literature SDA3A_U05, SDA3A_U01 Egzamin
M_U002 Student can construct mathematical models used in specific applications of advanced mathematics SDA3A_U06, SDA3A_U01 Kolokwium
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
45 30 15 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 Student can search for information in the literature, also in foreign languages + - - - - - - - - - -
M_W002 Student has in-depth knowledge in the chosen field of theoretical or applied mathematics + - - - - - - - - - -
Umiejętności
M_U001 Student speaks English at intermediate level (B2) at a level sufficient for reading literature - + - - - - - - - - -
M_U002 Student can construct mathematical models used in specific applications of advanced mathematics - + - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 157 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 45 godz
Przygotowanie do zajęć 30 godz
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 15 godz
Samodzielne studiowanie tematyki zajęć 60 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Dodatkowe godziny kontaktowe 5 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (30h):

1. Groups, automorphism groups of graphs as permutation groups. Graphs with abelian, vertex transitive, edge transitive, and primitive groups.
2. Cayley graphs, hypercubes (finite and infinite).
3. Automorphism breaking, motion, cost.
4. Infinite trees, groups acting freely on trees, Nielsen-Schreier Theorem.
5. Equivalence of the axiom of choice and the fact that connected graphs have spanning trees.
6. Kőnig’s Infinity Lemma.
7. Automorphism breaking of finite and infinite cubic graphs.
8. Ends of graphs, Halin’s theorems on ends, Halin’s theorem on graphs with a finite basis (and infinite motion).
9. Two-ended graphs, graphs with countable groups.
10. The Rado graph.
11. Compact graphs and trees. Theorems of Polat and Sabidussi, an algorithm to compute the distinguishing number of finite trees.
12. Trees with bounded valence and their distinguishing number in dependence of motion.
13. Infinite Motion Conjecture for edge colorings.
14. Density vs. cost in infinite graphs.

Ćwiczenia audytoryjne (15h):

Tutorials will focus on examples and applications. The aim is to make the students feel at ease with the material, to deepen the comprehension, to understand the role of symmetries in graphs, and to encourage independent mathematical thinking in general.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Classical blackboard lectures.
  • Ćwiczenia audytoryjne: Students attempt to solve problems on a blackboard, the teacher moderates the discussion and provides relevant explanations on an ongoing basis.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

There will be two small tests to check comprehension of definitions and basic results, a mid-term test and a final exam.

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Nie
    – Zasady udziału w zajęciach: Nie określono
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Nie określono
Sposób obliczania oceny końcowej:

Final mark will be the exam result (taking into account the tests and activity on excercises)

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

Students who are absent at a written test should ask for an additional date.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Student is aware with basics of graph theory and group theory.

Zalecana literatura i pomoce naukowe:

1. R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition, Taylor & Francis Group, New York, 2011.

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

1. M. Grech, W. Imrich, A. D. Krystek, Ł. J. Wojakowski, Direct product of automorphism groups of digraphs, Ars Math. Contemp. 17(1): 89-101 (2019).

2. I. Broere, W. Imrich, R. Kalinowski, M. Pilśniak, Asymmetric colorings of products of graphs and digraphs, Discrete Appl. Math. 266: 56-64 (2019).

3. R. Hammack, W. Imrich, Vertex-Transitive Direct Products of Graphs. Electr. J. Comb. 25(2): P2.10 (2018).

4. W. Imrich, I. Peterin, Cartesian products of directed graphs with loops. Discrete Math. 341(5): 1336-1343 (2018).

5. W. Imrich, R. Kalinowski, M. Pilśniak, M. Shekarriz, Bounds for Distinguishing Invariants of Infinite Graphs. Electr. J. Comb. 24(3): P3.6 (2017).

6. E. Estaji, R. Kalinowski, M. Pilśniak, T. Tucker, Distinguishing Cartesian products of countable graphs. Disc. Math. Graph Theory 37(1): 155-164 (2017).

7. M. Hellmuth, W. Imrich, W. Klöckl, P. Stadler, Local algorithms for the prime factorization of strong product graphs. CoRR abs/1705.03823 (2017).

8. T. Boiko, J. Cuno, W. Imrich, F. Lehner, Ch. E. van de Woestijne: The Cartesian product of graphs with loops. Ars Math. Contemp. 11(1): 1-9 (2016).

9. S. Chandran, W. Imrich; R. Mathew, D. Rajendraprasad, Boxicity and cubicity of product graphs.
Eur. J. Comb. 48, 100-109 (2015).

10. W. Imrich, S. Smith, T. Tucker, M. Watkins, Infinite motion and 2-distinguishability of graphs and groups. J. Algebr. Comb. 41, No. 1, 109-122 (2015).

Informacje dodatkowe:

The lectures will be led by prof. Wilfried Imrich (Montanuniversität Leoben, Austria)