Sparsity

elective monographs

Discrete mathematics 1000-212bMD

The knowledge of courses Algorithmics, Computational complexity and Logics for Computer Scientists will sometimes be helpful, but is not required.

Classroom

The course gives an introduction to the theory of sparse graphs, a research area within graph theory. Apart from investigating combinatorial properties of abstract notions of sparsity, like graph classes of bounded expansion and nowhere dense graph classes, the course also presents rich connections of the theory with algorithm design, extremal graph theory, and model theory.

Note: Course given in English

1. Measuring sparsity, definitions of bounded expansion and nowhere denseness, relation between shallow minors and shallow topological minors (2-3 lectures).

2. Generalized coloring numbers: combinatorics, algorithmic aspects and applications (2 lectures).

3. Low treedepth colorings: combinatorics and applications (1 lecture)

4. Model-checking First-Order logic on classes of bounded expansion (1 lecture)

5. Neighborhood complexity (1 lecture)

6. Quasi-wideness and splitter game (1-2 lectures)

7. VC-dimension and elements of stability theory (2 lectures)

8. Polynomial expansion and separators: applications to approximation algorithms (1-2 lectures)

J. Nešetřil, P. Ossona de Mendez, “Sparsity - Graphs, Structures, and Algorithms”.

Notes from the previous edition of the course.

Notes and research papers provided by the lecturers.

Knowledge:

The student knows various equivalent definitions of sparsity of graphs: classes of bounded expansion and nowhere dense graph classes, and understands connections between them. They can explain example applications of the theory of sparse graphs with particular focus on the design of parameterized and approximation algorithms. (K_W01, K_W02)

Skills:

The student can apply the combinatorial notions of sparsity in solving mathematical and algorithmic problems, including problems appearing in research. (K_U02, K_U09)

Competences:

The student knows the limitations of his/her own knowledge and the need of further study, and in particular the necessity of obtaining knowledge from the outside of the field (K_K01). They can formulate precise questions in order to deepen own understanding of the topic or to find the missing pieces of the reasoning (K_K02). The student understands the need to systematically read scientific articles to broaden and expand his/her knowledge (K_K08).

Homeworks (around 50%) and oral exam (around 50%)

The course can provide credit for doctoral students as a "methodological course". In that case, there is an additional requirement for passing the course: the student should correctly solve at least one of the more difficult problems from homeworks, designated by the instructors as a "research problem".