Test
Freitag, 7.4.17, 12:00-13:00, Hörsaal II, Albertstr. 23b
Bla bla
Test
Mittwoch, 12.4.17, 12:00-13:00, Hörsaal II, Albertstr. 23b
Applications of ultraproducts of finite structures to Combinatorics
Mittwoch, 19.4.17, 16:00-17:00, Raum 404, Eckerstr. 1
The fundamental theorem of ultraproducts (Łos' Theorem) provides a transference principle between the finite structures and their limits. Roughy speaking, it states that a formula 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.\n\nWhen applied to ultraproducts of finite structures, Łos' theorem presents an interesting duality between finite structures and their infinite ultraproducts. This kind of finite/infinite connection can sometimes 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 model-theoretic properties in their ultraproducts.\n\nThese ideas were used by Hrushovski to apply ideas from geometric model theory to additive combinatorics, locally compact groups and linear approximate subgroups. More examples of this fruitful interaction were given by Goldbring and Towsner to provide proofs of the Szemerédi's regularity lemma and Szemerédi's theorem: every subset of the integers with positive density contains arbitrarily large arithmetic progressions. \n\nThe purpose of the talk will be to present these ideas and outline some of the applications to asymptotic 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.\n\n