LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Seminar
Counting homomorphisms between finite structures
- Date
- 1.12.2020, 10:45
- Place
- online
- Speaker
- Luca Reggio (University of Oxford)
A celebrated result of Lovasz (1967) states that two finite relational structures A and B are isomorphic precisely when the sets of homomorphisms Hom(C,A) and Hom(C,B) have the same cardinality for every finite structure C. Since then, homomorphism counting results have played an important role in graph theory and finite model theory. We introduce a categorical framework where an abstract Lovasz-type result can be proved. Exploiting the theory of game comonads (introduced by Abramsky, Dawar et al.), we are able to recover in a systematic way homomorphism counting results of Dvorak (2009) and Grohe (2020) for finite structures of bounded tree-width and tree-depth, respectively, as well as prove new ones. - This is joint work with Anuj Dawar and Tomas Jakl (University of Cambridge).