AlgoMaNet - spring 2020
Registration
The registration is free.
To register, send an e-mail to Darina Boukalová (boukalova3cjQFX02Z@fiKhu58XAO9.munixtQ4E8Cug.cz)
by October 18, 2019 October 22, 2019.
Please register even if you intend to attend a locally organized course.
In your registration e-mail, please indicate
who you are (your name and affiliation in particular),
which lectures you would like to attend and
what level of support is necessary for you to participate.
We may be able to accept registrations by students not affiliated with either of the four universities in the network. These registrations will be confirmed after the registration deadline if space constraints permit.
Courses in Warsaw, January 13 - January 24, 2020
The courses will take place at the Faculty of Mathematics, Informatics and Mechanics of the Warsaw University in its building located at Banacha 2, Warsaw. The lectures in Week 1 take place on Monday, Tuesday and Wednesday, and in Week 2 on each of the days.
Week 1: January 13-16
| Jan 13, 10:15 - 12:15 | Automata, semigroups and logic (room 2180, lecture, with break) |
| Jan 13, 13:15 - 15:30 | Automata, semigroups and logic (room 2180, tutorial, with break) |
| Jan 14, 10:15 - 12:15 | Automata, semigroups and logic (room 3250, lecture, with break) |
| Jan 14, 13:15 - 15:30 | Automata, semigroups and logic (room 5050, tutorial, with break) |
| Jan 15, 10:15 - 12:15 | Automata, semigroups and logic (room 4070, lecture, with break) |
| Jan 15, 13:15 - 15:30 | Automata, semigroups and logic (rooms 3170 and 3220, tutorial, with break) |
| Jan 16, 10:15 - 12:15 | Automata, semigroups and logic (room 2180, tutorial/informal meeting) |
Week 2: January 20-24
| 10:15 - 11:45 | Combinatorics and algorithms for sparse graphs (room 2180, lecture) |
| 12:45 - 14:15 | Combinatorics and algorithms for sparse graphs (room 2180, tutorial) |
Syllabus for the course "Automata, semigroups and logic"
For a language of finite words, the following conditions are equivalent: (a) it is regular, i.e. recognised by a finite automaton; (b) it can be defined by a formula of monadic second-order logic; (c) it is recognised by a homomorphism into a finite semigroup. I will talk about these connections, with a certain emphasis on the semigroups in item (c). In particular, I would like to talk about Green’s relations, which explain much of the behaviour of finite semigroups.
Syllabus for the course "Combinatorics and algorithms for sparse graphs"
The course will be an introduction to the theory of sparse graphs, a young branch of graph theory that studies abstract notions of structural sparseness in graphs. After introducing the main concepts - bounded expansion and nowhere denseness - we will present several combinatorial methods and viewpoints that are fundamental for the theory, including generalized coloring numbers, low treedepth colorings, neighborhood complexity, and uniform quasi-wideness. We will also show some applications of those techniques in algorithm design and in algorithmic finite model theory.
Courses in Brno, January 27 - February 7, 2020
The courses will take place at the Faculty of Informatics of Masaryk University. On each of the workdays, there will be a lecture from two of the courses in the morning. In addition to the lectures, the lecturers will also be available to discuss the exercise problems given during the morning lectures in the afternoon.
Week 1: January 27 - January 31, 2020
| 9:00 - 10:30 | Regularity method (room A318) |
| 11:00 - 12:30 | Extremal graph theory (room A318) |
| 15:00 | Informal meeting over exercise problems, student presentations (room C417) |
Week 2: February 3, 2020
| 10:00 - 11:30 | Extremal graph theory (room A318) |
| 13:00 - 14:30 | Topological and geometric graph theory (room A318) |
| 15:00 | Informal meeting over exercise problems, student presentations (room C417) |
Week 2: February 4-February 7, 2020
| 9:00 - 10:30 | Topological and geometric graph theory (room A318) |
| 11:00 - 12:30 | Extremal graph theory (room A318) |
| 15:00 | Informal meeting over exercise problems, student presentations (room C417) |
Syllabus for the course "Extremal graph theory"
The course will cover basic concepts in the extremal graph theory, including Turán's theorem and its generalizations, as well as important methods related with bipartite Turán problems and techniques of embedding large (spanning) graphs. Except the classical theorems, some recent results and open problems will be also presented.
Syllabus for the course "Topological and geometric graph theory"
This short course will provide basic knowledge of topological graph theory. This includes surfaces and graphs embedded in them, cycles in embedded graphs and some other embedding properties, and embedding density. In addition to classical topological graph questions, we will address the particular problem of graph crossing number, and focus on the related structural results including the very recent progress in the area. Lastly, we will mention several interesting questions of geometric representations of graphs.
Prerequisities: We assume mild undergraduate knowledge of topology (continuous maps, limits, compactness, homeomorphisms) and of graphs (minors, planar graphs, Euler's formula).
Syllabus for the course "Regularity method"
The regularity method is one of the most important tools in modern combinatorics. Szemerédi's Regularity Lemma from the late 1970s asserts that every graph can be partitioned into a bounded number of parts that mutually interact in a pseudorandom way. This important result has found many applications in various areas of mathematics and computer science, in particular, in extremal combinatorics and property testing, and has been generalized from the graph setting to many other combinatorial objects. During the lectures, we will present the Regularity Lemma and its counting counterpart, the Removal Lemma, in the setting of graphs, groups, hypergraphs and permutations. We will also present several applications of the regularity method in extremal combinatorics.
Courses in Prague, May 4 - May 15, 2020
The two courses planned at Charles University had to be cancelled because of the restrictions related to the coronavirus pandemic.
Participation of Charles University in the network is supported by the RSJ foundation.