University of Birmingham > Talks@bham > Theoretical computer science seminar > Lovász' Theorem and Comonads in Finite Model Theory

## Lovász' Theorem and Comonads in Finite Model TheoryAdd to your list(s) Download to your calendar using vCal - Tomáš Jakl, Cambridge University, https://www.cl.cam.ac.uk/~tj330/
- Friday 25 September 2020, 13:50-15:00
- https://bham-ac-uk.zoom.us/j/91939191081?pwd=THdqTXRsRWl1aDl5VDhTN2thckt6UT09.
If you have a question about this talk, please contact Martin Escardo. The talk is at 2pm. We start at 1:50 for socializing with the speaker. In this talk I will present our joint work with Anuj Dawar and Luca Reggio. More than 50 years ago László Lovász showed that, in order to determine an isomorphism of two finite relational structures, it is enough to test that they both admit the same number of homomorphisms from any other finite structure. This result has been revisited recently by Zdeněk Dvořák and Martin Grohe. They showed that instead of an isomorphism we obtain a logical equivalence w.r.t a fragment of first-order logic, if we restrict the test structures to a given smaller category. We proved that all three of the above results can be captured in the framework of Samson Abramsky, Anuj Dawar, et al. The framework uses graded comonads to capture various combinatorial and logical properties of relational structures. Our new proofs make use of the graded comonads. As a byproduct we obtain a new result for modal logic simply by changing the graded comonad in question. This talk is part of the Theoretical computer science seminar series. ## This talk is included in these lists:- Computer Science Departmental Series
- Computer Science Distinguished Seminars
- Theoretical computer science seminar
- https://bham-ac-uk.zoom.us/j/91939191081?pwd=THdqTXRsRWl1aDl5VDhTN2thckt6UT09
Note that ex-directory lists are not shown. |
## Other listsFeatured lists Geometry and Mathematical Physics seminar Birmingham and Warwick Algebra Seminar## Other talksTBA An optimal approximation algorithm for Feedback Vertex Set in Tournaments Modelling nanoplasmonic hot carrier generation Non-stationary quantum many-body dynamics Graphical approximations of Matern Gaussian fields: theory and applications Medical Image Analysis with Data-efficient Learning |