AlgoMaNet - spring 2022

Basic information

The two AlgoMaNet courses scheduled for the spring 2022 will take place in the week May 23-27 at the Jagiellonian University in Kraków. The courses will be delivered on site only. The registration for the courses is now closed.

Schedule

All lectures and exercices take part in the building of the Faculty of Mathematics and Information Technologies at ulica Prof. S. Łojasiewicza 6, Kraków.

Monday May 23

Tuesday May 24

Wednesday May 25

Thursday May 26

Friday May 27

Gwenaël Joret: Product structure of planar graphs

The course will focus on the following "product structure theorem" for planar graphs: Every planar graph G is a subgraph of the strong product of a graph H of treewidth 8 and a path P. Treewidth is a measure of similarity to a tree, and many combinatorial / algorithmic problems on graphs become easy when restricted to trees, or more generally, to graphs of bounded treewidth. One can thus think of the product structure theorem as a tool for extending results that are known to hold for bounded treewidth graphs to planar graphs. Indeed, a number of old open problems about planar graphs have been solved recently in this way, such as bounding the queue-number and the nonrepetitive chromatic number by a constant, designing an adjacency labeling scheme using only log₂n bits roughly, and building universal graphs with few edges. Besides covering the product structure theorem and its applications, the course will also cover some other related decomposition results for planar graphs, and generalizations of the theorem beyond planar graphs.

Piotr Micek: Combinatorics of posets

Graphs and posets are ubiquitous combinatorial structures. They model numerous objects within set theory, topology, algebra and theoretical computer science. The most important measure of a graph's complexity is the chromatic number. What do the graphs with large chromatic number look like? Which structures are forced to appear together with large chromatic number? The structure graph theory provides a wealth of concepts and results for coping with this type of questions. Similarly, the dimension, introduced by Dushnik and Miller in 1941, is a key parameter of a poset's complexity. What do the posets with large dimension look like? Which structures are forced to appear with large dimension? These questions are sound and present since at least 1970's but only recently we developed the right tools and started to methodically answer them. Within these lectures we will cover the recent development with a special emphasis on posets with sparse cover graphs.

Participation of Charles University in the network is supported by the RSJ foundation.