BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T132812Z
UID:Seminar-dept-620@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20200526T130000
DTEND:20200526T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Viktor Zamaraev: Implicit Graph Representation Conjecture and Geometric Intersection Graph Classes\n\nAn adjacency labeling scheme for a graph class is an assignment of labels to the vertices of each graph in the class such that the adjacency of two vertices in the graph can be determined solely by the labels of these vertices. The labels are binary strings of the same length and the goal is to make the labels as short as possible. \n\n\n\nIf one wants to encode node identifiers within the labels, the size of the labels should be \Omega(\log n) bits, where n is the size of the graph. A natural question is what families of graphs admit adjacency labeling schemes with \Theta(\log n) bits. In particular, does every graph family with the "right" number of graphs admit such a labeling scheme? In 1992, Kannan, Naor, and Rudich showed that the answer to this question is negative in general. However, for hereditary graph classes, the question remains open since then.\n\n\n\nThe aim of this talk is to discuss the Implicit Graph Representation Conjecture, its connection to geometric intersection graph classes, and present some open problems surrounding the conjecture.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=620
LOCATION:Microsoft Teams
END:VEVENT
END:VCALENDAR