BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Number of quantifiers in 3-variable logic on linear orders - Lauri
  Hella (Univeristy of Tampere)
DTSTART:20250321T140000Z
DTEND:20250321T150000Z
UID:TALK228991@talks.cam.ac.uk
CONTACT:Anuj Dawar
DESCRIPTION:Grohe and Schweikardt proved in 2005 that the smallest sentenc
 e of 3-variable logic FO^3^ that can separate a linear order of length n f
 rom all shorter linear orders is of length at least O(√n). The best uppe
 r bound for the length of such a sentence that we found in the literature 
 is O(n).\n\nIn this talk I present a new game that characterizes definabil
 ity by sentences of FO^k^ with n quantifiers. Using this game I show that 
 there is a sentence of FO^3^ with 2m+1 quantifiers that is true in a linea
 r order if and only if its length is at least 2m(m+1)+1. Furthermore\, I s
 how a matching lower bound result using the game: all linear orders of len
 gth at least 2m(m+1)+1 are equivalent with respect to all sentences of FO^
 3^ with at most 2m+1 quantifiers. The first of these results implies O(√
 n) upper bound for the length of a sentence of FO^3^ needed for separating
  linear orders of length n from shorter linear orders.\n\n(joint work with
  Kerkko Luosto)
LOCATION:SS03\, Computer Laboratory
END:VEVENT
END:VCALENDAR