Lovász' Theorem and Comonads in Finite Model Theory

Add to your list(s) Download to your calendar using vCal

• Tomas Jakl, University of Cambridge
• Friday 13 November 2020, 14:00-15:00
• Online.

If you have a question about this talk, please contact Jamie Vicary.

https://us02web.zoom.us/j/177472153?pwd=MFgwd0EzY05QSGtpSDc2dU16aG9wdz09

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 Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• Online
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.