Sparsity DocCourse Prague 2018
An intensive program for senior undegraduate and graduate students devoted to the study of sparse combinatorial structures in the context of model theory.
Dates: Nov 4 – Dec 15 2018Place: Charles University, Prague
Main Organisers: Jaroslav Nešetřil
Assistents: Matěj Konečný, Jan Hubička
Expected tuturials by
- Z. Dvořák (Prague)
- J. Nešetřil (Prague)
- D. Kráľ (Brno)
- P. Ossona de Mendez (Paris, Prague)
- Ma. Pilipczuk (Warsaw)
- Mi. Pilipczuk (Warsaw)
- S. Siebertz (Berlin)
- P. Simon (Berkeley)
- B. Sullivan (NCSU)
- S. Toruńczyk (Warsaw)
- F. Reidl (London)
- J. Gajarský (Berlin)
Preliminary schedule
(Subject to changes.) The lectures, which are typically 90 minutes long, will take place at the building of Charles University, Malostranské náměstí, 25, Prague. Problem solving sessions will take place on the corridor on the 2nd floor whenever there is no lecture.| Date | Time | Room | Speaker | Title |
|---|---|---|---|---|
| Week 1 | ||||
| Monday, November 5 | 14:00 | S6 | Opening ceremony | |
| Monday, November 5 | 14:30–17:10 | S6 | J. Nešetřil & P. Ossona de Mendez | There is depth in shallowness |
| Wednesday, November 7 | 10:40 | S6 | Z. Dvořák | Polynomial expansion |
| Wednesday, November 7 | 14:00 | S10 | P. Ossona de Mendez | How orientations can make things simpler |
| Thursday, November 8 | 12:20 | S9 | P. Ossona de Mendez | Why everything get even easier when you follow orders |
| Friday, November 9 | 14:00 | S10 | Z. Dvořák | Dominating and independent sets |
| Friday, November 9 | 15:40 | S10 | S. Toruńczyk | Model checking first-order logic on graphs of bounded expansion |
| Week 2 | ||||
| Monday, November 12 | 14:00 | S6 | S. Toruńczyk | Model checking first-order logic on graphs of bounded expansion |
| Monday, November 12 | 15:40 | S6 | P. Simon | Introduction to model theory and stability |
| Tuesday, November 13 | 17:10 | S3 | S. Toruńczyk | Sparseness and stability |
| Wednesday, November 14 | 10:40 | S6 | P. Simon | Introduction to model theory and stability |
| Wednesday, November 14 | 14:00 | S10 | P. Simon | Introduction to model theory and stability |
| Thursday, November 15 | 14:00 | S4 | P. Simon | Introduction to model theory and stability |
| Thursday, November 15 | 15:40 | S10 | D. Kráľ | Introduction to limits of sparse graphs |
| Friday, November 16 | 14:00 | S10 | Mi. Pilipczuk | Algorithms for domination and independence using uniform quasi-wideness |
| Friday, November 16 | 15:40 | S10 | D. Kráľ | Introduction to limits of sparse graphs |
| Week 3 | ||||
| Monday, November 19 | 9:00 | S1 | P. Simon | Introduction to model theory and stability |
| Monday, November 19 | 14:00 | S6 | Mi. Pilipczuk | Neighborhood complexity: the bounded expansion case |
| Tuesday, November 20 | 14:00 | S510! | Mi. Pilipczuk | Polynomial bounds for centered colorings on planar graphs |
| Wednesday, November 21 | 10:40 | S6 | J. Gajarský | Interpretations – how to speak about sparsity in dense graphs (slides) |
| Wednesday, November 21 | 14:00 | S10 | Mi. Pilipczuk | Neighborhood complexity: the nowhere dense case and extension to types |
| Friday, November 23 | 14:00 | S10 | Mi. Pilipczuk | Kernelization for domination on classes of sparse graphs |
| Friday, November 23 | 15:40–17:00! | S10 | Ma. Pilipczuk | Computing sparsity stuff in real world graphs: generalized coloring numbers |
| Week 4 | ||||
| Sunday, November 25 | afternoon | Departure to Český Krumlov | ||
| Monday, November 26 | Č. Krumlov | B. Sullivan & F. Reidl | Complex networks and sparsity I | |
| Complex networks and sparsity II | ||||
| Tuesday, November 27 | Complex networks and sparsity III | |||
| Complex networks and sparsity IV | ||||
| Wednesday, November 28 | Č. Krumlov | P. Ossona de Mendez | Converging to Structural Limits | |
| Wednesday, November 28 | afternoon | Č. Krumlov | Return to Prague | |
| Thursday, November 29 | 12:20 | S9 | P. Ossona de Mendez | Limits and Beyond |
| Friday, November 30 | 14:00 | S10 | J. Gajarský | Interpretations – how to speak about sparsity in dense graphs (slides) |
| Friday, November 30 | 15:40 | S10 | F. Reidl | Meta-kernelization and sparsity |
| Week 5 | ||||
| Monday, December 3 | ITI Fest | |||
| Tuesday, December 4 | ITI Fest | |||
| Wednesday, December 5 | ITI Fest: 4 Mathematical colloquia (U. Feige, M. Szegedy, M. Noy, M. Thorup) | |||
| Thursday, December 6 | 15:40 | S10 | Ma. Pilipczuk | Computing sparsity stuff in real world graphs: uniform quasi-wideness |
| Thursday, December 6 | 17:20 | S11 | M. Noy | Limiting probabilities of FO and MSO properties of random graphs from minor-closed classes |
| Friday, December 7 | 14:00 | S10 | B. Sullivan | What’s really needed for “theory in practice”? |
| Friday, December 7 | 15:40 | S10 | B. Szegedy | Action convergence of operators and graphs |
| Week 6 | ||||
| Monday, December 10 | 14:00 | S6 | Z. Dvořák | Fragility |
| Wednesday, December 12 | S6 | Final projects | ||
| Friday, December 14 | Final projects | |||
Preparatory course
- Wednesday, October 10 (Jan Hubička): Introduction to model theory part I. Recommended reading:
- Wednesday, October 17 (Matěj Konečný): Introduction to model theory part II. Elementary equivalence, embeddings, complete theories (examples: dense linear orders, algebraically closed fields, real closed fields, theory of the random graph), more on definable sets (examples and quantifier elimination), types.
- Wednesday, October 24 (Matěj Konečný): More types, definable relations, stability, NIP.
Supported by Charles University in the framework of 4EU agreement of universities Heidelberg, Paris, Prague and Warsaw. If you want to participate then please send your CV and a letter of recommendation to doccourse2018@iuuk.mff.cuni.cz
