Le théorème de Fagin-GKLT : histoire d’un aller et retour

by Baptiste Schilling (ICJ)

Wednesday Feb 5, 2025, 10:30 AM → 12:30 PM Europe/Paris

Fokko du Cloux (ICJ)

Le théorème de Fagin-GKLT porte sur le comportement asymptotique de la proportion de graphes finis satisfaisant certaines propriétés, dites « du premier ordre ». Dans cet exposé, je présenterai une démonstration de ce théorème par la théorie des modèles infinis, ce qui nous permettra de rencontrer plusieurs des théorèmes et techniques fondamentales de théorie des modèles. Si le temps me le permet, je discuterai également des généralisations possibles de ce théorème, en passant à des logiques plus expressives.