BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260726T073824Z
UID:Seminar-dept-1028@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230314T130000
DTEND:20230314T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Maksim Zhukovskii: First order complexity of random structures\n\nThe classical 0-1 law for first order logic states that for any finite relational signature its random uniform n-structure obeys the 0-1 law, i.e. every first order sentence is either true with asymptotical probability 1, or false with asymptotical probability 1. It can be viewed as the triviality of first order behaviour of such distributions. For other distributions the behaviour changes and becomes more complex. In particular, it is known that sparse random graphs with probability of appearance of an edge p=n^{-a} does not obey even the first order convergence law for rational a, while when p=c/n the convergence law holds, and the set of limits is well studied. We introduce the notion of first order complexity of random structures, present a natural hierarchy of complexity classes and define a reduction that, in particular, can be used to transfer 0-1 laws between random structures.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1028
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR