Selected topics in graph theory

elective monographs

During the course we shall discuss a series of topics from modern graph theory from the classical (i.e., non-algorithmic) point of view.

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.

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

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)

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.