BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T121952Z
UID:Seminar-dept-1271@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250311T130000
DTEND:20250311T140000
SUMMARY:School Seminar Series
DESCRIPTION:Tomáš Hons: A polynomial Ramsey statement for bounded VC-dimension\n\nZoom link: https://liverpool-ac-uk.zoom.us/j/98935123903?pwd=SaYbdu6qHaNPqbJbdVb3hVDBRnIgPy.1\n\nMeeting ID: 989 3512 3903\n\nPasscode: CSLiver#1 \n\n\n\nA theorem by Ding, Oporowski, Oxley, and Vertigan states that every sufficiently large bipartite graph without twins contains a matching, co-matching, or half-graph of arbitrary size as an induced subgraph. We prove that this Ramsey statement has polynomial dependency assuming bounded VC-dimension of the initial graph, using the recent verification of the Erd\H{o}s-Hajnal property for graphs of bounded VC-dimension. Since the theorem of Ding et al. plays a role in (finite) model theory, which deals with even more restricted structures, we also comment on its further refinements in this context.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1271
LOCATION:ELEC204, 2th Floor Lecture Theatre EEE
END:VEVENT
END:VCALENDAR