IPM

                                پژوهشگاه دانش‌های بنیادی
پژوهشکدهٔ ریاضیات


Mathematical Logic Weekly Seminar سمینار هفتگی منطق ریاضی




TITLE  
Model Theory of Tame Classes of Finite Structures


SPEAKER  
Anuj Dawar  
University of Cambridge, England  
 


TIME  
Thursday, November 28, 2024,   14:00 - 16:00


VENUE   Lecture Hall 1, Niavaran Bldg.



SUMMARY

 

The class of finite structures is a notoriously ill-behaved one from the point of view of model theory. In the early years of this century, this led to the study of subclasses of this class which exhibit better behaviour. The focus was on classes defined by the sparsity of their underlying Gaifman graph. Such sparse classes were shown to be well-behaved in model-theoretic and algorithmic terms. The good behaviour discussed there focused on two aspects: that such classes show preservation properties that fail on the class of finite structures, and evaluation of first-order formulas is algorithmically tractable in such classes. A common theme is the use of the locality of first-order logic which, in the absence of compactness, is a key tool of finite model theory. More recent work has sought to extend this work to classes of finite structures that are not sparse, and identify tame classes of dense structures. This has seen a convergence with notions of tameness coming from stability theory.
In this talk, I review the use of locality in identifying tame classes; discuss the tameness of some sparse classes; and present some recent extensions to dense classes and the connections with stability.

Zoom room information:
https://us06web.zoom.us/j/81916335336?pwd=5zQT4lutMiBoY5Xp1pkFGtbqiaGozg.1
Meeting ID: 819 1633 5336
Passcode: 559618

 




تهران، ضلع‌ جنوبی ميدان شهيد باهنر (نياوران)، پژوهشگاه دانش‌های بنيادی، پژوهشکده رياضيات
School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Niavaran Bldg., Niavaran Square, Tehran
ipmmath@ipm.ir   ♦   +98 21 22290928   ♦  math.ipm.ir