Lematy o regularności

Seminarium: 
Teoria modeli
Osoba referująca: 
Tomasz Rzepecki
Data: 
środa, 16. Listopad 2016 - 16:15
Sala: 
604
Opis: 

Lemat Szemerédiego o regularności, w pewnym uproszczeniu, mówi że każdy dostatecznie duży graf można podzielić na pewną skończną liczbę części (niezależną od wielkości grafu) o prawie jednakowym rozmiarze, tak że prawie każda para części zachowuje się jak "graf losowy". Znajduje on zastosowanie w teorii grafów, teorii liczb oraz kombinatoryce ekstremalnej.

Wadą lematu jest to, że wielkość grafu konieczna do uzyskania pożądanej "losowości" rośnie bardzo szybko (szybciej niż każda funkcja wykładnicza). Okazuje się jednak, że gdy ograniczymy stopień skomplikowania grafu (np. gdy zażądamy, by był on definiowalny w ciele skończonym, lub rzeczywistym), można uzyskać dużo lepsze szacowania.

W czasie seminarium opowiem o niektórych wariantach i wnioskach z lematu Szemerédiego dla teorii stabilnych i NIP, wraz z powiązaną terminologią, oraz udowodnię wersję lematu dla teorii stabilnych w wersji udowodnionej przez Malliaris oraz Pillay'a.