BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: The notions of bounded expansion and nowhere denseness capture
  uniform sparseness of graph classes and render various algorithmic problem
 s that are hard in general tractable. In particular\, the model-checking pr
 oblem for first-order logic is fixed-parameter tractable over such graph cl
 asses. With the aim of generalizing such results to dense graphs\, we intro
 duce structurally bounded expansion and structurally nowhere dense graph cl
 asses\, dfined as first-order interpretations of bounded expansion and nowh
 ere dense graph classes. As a first step towards their algorithmic treatmen
 t\, we provide a characterization of structurally bounded expansion classes
  via low shrubdepth decompositions\, a dense analogue of low treedepth deco
 mpositions. We prove that structurally nowhere dense graph classes are vc-m
 inimal. 
DTSTAMP:20181113T131200
DTSTART:20181126T160000
CLASS:PUBLIC
LOCATION:Humboldt-Universität zu Berlin\n Institut für Informatik\n Humbold
 t-Kabinett (between House 3&4 / 1st Floor [British Reading])\n Johann von N
 eumann-Haus\n Rudower Chaussee 25\n 12489 Berlin
SEQUENCE:0
SUMMARY:Sebastian Siebertz (Humboldt-Universität zu Berlin): First-order in
 terpretations of sparse graph classes
UID:94625241@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20181126-C-Sie
 bertz.html
END:VEVENT
END:VCALENDAR