Selected topics in graph theory 1000-2M12WTG
During the course we shall discuss a series of topics from modern graph theory from the classical (i.e., non-algorithmic) point of view.
We selected the following topics:
1. Expander graphs. Definition, constructions, applications (L=SL).
2. Minor theory. Robertson-Seymour theorem, examples. Decomposition theorems. Structural graph parameters (treewidth and others).
3. Colourings. The discharging method. The four-colour theorem. Brooks' theorem, Vizing theorem. Perfect graphs.
Type of course
Course coordinators
Learning outcomes
Knowledge:
The student has advanced knowledge on the following three fields on the border between mathematics and computer science:
* minor theory and its applications in algorithm theory
* expanders and spectral graph theory
* graph colourings.
(K_W01, K_W02)
In particular, the student is able to understand an advanced usage of these techniques in a studied material (e.g., research article) and realize the need to use them in his own work.
Skills:
* can use new techniques in own research work (K_U01)
* can use literature and research articles (in English) (K_U14)
Competences
* understands the need to systematically read scientific articles to broaden and expand knowledge (K_K08)
* can formulate precise questions to deepen own understanding of the topic or to find the missing pieces of the reasoning (K_K02)
Assessment criteria
There will be 3 sets of homework problems, each consisting of 4 problems, resulting in a modifier to the exam grade from the interval [-1, +1.5]. Moreover, after each lecture there will be a short quiz in Moodle; solving all quizzes within their respective deadlines is a requirement to be admitted to the exam in the first session period. The exam will be an oral one.
Bibliography
Books:
Reinhard Diestel, Graph Theory, Springer-Verlag 2005. Wersja elektroniczna: http://diestel-graph-theory.com/GrTh.html
Bela Bollobas, Modern Graph Theory, Springer 1998.
Mike Krebs, Anthony Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide, Oxford University Press, USA, 2011.
Surveys and lecture notes available on the Internet, among other:
Shlomo Hoory, Nathan Linial, Avi Wigderson, Expander Graphs and Their Applications, Bulletin of AMS 2006.
http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
Michael A. Nielsen, Introduction to Expander Graphs, 2005.
http://www.qinfo.org/people/nielsen/blog/archive/notes/expander_graphs.pdf
Laszlo Lovasz, Graph Minor Theory, Bulletin of AMS 2005.
http://www.ams.org/bull/2006-43-01/S0273-0979-05-01088-8/S0273-0979-05-01088-8.pdf
Petr Hlineny, Discharging Technique in Practice.
http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: