BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Lovász' Theorem and Comonads in Finite Model Theory - Tomas Jakl\
 , University of Cambridge
DTSTART:20201113T140000Z
DTEND:20201113T150000Z
UID:TALK152596@talks.cam.ac.uk
CONTACT:Jamie Vicary
DESCRIPTION:https://us02web.zoom.us/j/177472153?pwd=MFgwd0EzY05QSGtpSDc2dU
 16aG9wdz09\n\nIn this talk I will present our joint work with Anuj Dawar a
 nd Luca\nReggio.\n\nMore than 50 years ago László Lovász showed that\, 
 in order to determine\nan isomorphism of two finite relational structures\
 , it is enough to test\nthat they both admit the same number of homomorphi
 sms from any other\nfinite structure. This result has been revisited recen
 tly by Zdeněk\nDvořák and Martin Grohe. They showed that instead of an 
 isomorphism we\nobtain a logical equivalence w.r.t a fragment of first-ord
 er logic\, if\nwe restrict the test structures to a given smaller category
 .\n\nWe proved that all three of the above results can be captured in the\
 nframework of Samson Abramsky\, Anuj Dawar\, et al. The framework uses\ngr
 aded comonads to capture various combinatorial and logical properties\nof 
 relational structures. Our new proofs make use of the graded\ncomonads. As
  a byproduct we obtain a new result for modal logic simply\nby changing th
 e graded comonad in question.
LOCATION:Online
END:VEVENT
END:VCALENDAR