BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Homomorphism Indistinguishability: Characterisations\, Closure\, C
 omplexity - Tim Seppelt (RWTH Aachen University)
DTSTART:20241015T130000Z
DTEND:20241015T140000Z
UID:TALK222808@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:In 1967\, Lovász proved that two graphs G and H are isomorphi
 c if and only if they are homomorphism indistinguishable over the the fami
 ly of all graphs\, i.e. for all graphs F the number of homomorphisms from 
 F to G is equal to the number of homomorphisms from F to H. In recent year
 s\, many natural relaxations of graph isomorphism from fields as diverse a
 s quantum information theory\, algebraic graph theory\, convex optimisatio
 n\, or category theory have been characterised as homomorphism indistingui
 shability relations over restricted graph classes.\n\nMotivated by the wea
 lth of such results\, we set out in this talk to develop a theory of homom
 orphism indistinguishability. We will focus on three themes:\n\n- Characte
 risations: How to characterise homomorphism indistinguishability relations
  in particular in terms of systems of equations such as the Sherali--Adams
  or Lasserre integer programming hierarchies?\n- Closure: How to compare t
 he expressiveness of homomorphism indistinguishability relations using too
 ls from structural graph theory?\n- Complexity: What is the complexity of 
 deciding whether two input graphs are homomorphism indistinguishable over 
 a given graph class?
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR