Mathematical Sciences Seminar - Applications of ultraproducts of finite structures to combinatorics
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
The fundamental theorem of ultraproducts (Los' Theorem) provides a transference principle between the finite structures and their limits. Roughy speaking, it states that a first-order statement is true in the ultraproduct M of an infinite class of structures if and only if it is true for "almost every" structure in the class.
When applied to ultraproducts of finite structures, Los' theorem presents an interesting connection between classes of finite structures and their infinite ultraproducts which can be used to prove qualitative properties of large finite structures using the powerful known methods and results coming from infinite model theory and, in the other direction, quantitative properties in the finite structures often induce desirable properties in their ultraproducts.
The purpose of the talk will be to present the ultraproduct construction, focusing on ultraproducts on finite structures, and outline some of the applications to asymptotic (extremal) combinatorics.
If time permits, I will give a brief overview of the Erdos-Hajnal conjecture and present a proof (due to A. Chernikov and S. Starchenko) of the Erdos-Hajnal property for graphs without the order property using ultraproducts, pseudofinite dimensions and basic properties of stable formulas.
Contact name:
Department of Economics, Mathematics and Statistics