Date: Fri, Apr 17, 2015
Time: 08:40 - 10:40
Venue: Room 3323
Title: Structure theory for graph homomorphisms: Homomorphisms and sparse graphs
The lecture contains the definition of sparse - dense dichotomy for graphs, stability and basic characterisations. As a case study, homomorphisms and logic are discussed. We finish with some algorithmic consequences.
No familiarity with the first part will be assumed.
Basic reference: J. Nešetřil, P. Osssona de Mendez: Sparsity - Graphs, Structures and Algorithms, Springer 2012.
Jaroslav Nešetřil received his Ph.D. from Charles University in 1975, became a full professor of geometry and topology at Charles University since 1993 and has published more than 300 publications, including 9 books and 18 artistic publications. Since 2006, he is the chairman of the Committee of Mathematics of Czech Republic.
Nešetřil is a corresponding member of the German Academy of Sciences since 1996, a fellow of the Czech Learned Society since 2004, a member of the Academia Europaea since 2012, an honorary member of the Hungarian Academy of Sciences since 2013. He received in 2010 the Medal of Merit of Czech Republic.
He was an invited speaker of the 5th European Congress of Mathematics (Amsterdam, 2008) and the International Congress of Mathematicians (Hyderabad, 2010).
He founded the European Conference on Combinatorics, Graph Theory and Applications in 2001 and organizes it every two years since then. He was a member of the program committee of the International Congress of Mathematicians (Seoul, 2014).
Slides: View slides