Sparsity 1000-2M12GRZ
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)
Type of course
Mode
Requirements
Prerequisites (description)
Course coordinators
Learning outcomes
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).
Assessment criteria
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".
Bibliography
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.
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: