Model-Theoretic Stability and its application to the Szemerédi Regularity Lemma

In questa tesi viene affrontata una delle strategie tramite le quali è possibile eliminare le coppie eccezionali che caratterizzano il Lemma di Regolarità di Szemerédi. Le coppie eccezionali sono quelle coppie di sottoinsiemi di nodi che non seguono le proprietà di regolarità dettate dal Lemma: esse sono inevitabili se si desidera mantenere la massima generalità. Una delle possibili limitazioni è la restrizione a grafi che, per un certo naturale k, esprimono la non-k-order property per la formula xRy, dove R è la relazione binaria di connessione tramite arco. Questo permette non solo di rimuovere la necessità di coppie eccezionali, ma anche di ottenere partizioni in sottoinsiemi indiscernibili con forti proprietà di regolarità.