Το Regularity Lemma Και Οι Εφαρμογές Του Στην Θεωρία Γραφημάτων

Abstract

Το Regularity Lemma, που πρωτοαναπτύχθηκε από τον Ούγγρο μαθηματικό Endre Szemeredi, είναι ένα χρήσιμο εργαλείο στην θεωρία γραφημάτων καθώς μας λέει ότι ένα οποιοδήποτε πυκνό γράφημα μπορεί να προσεγγιστεί από ψευδοτυχαία γραφήματα. Αυτό έχει πολλές εφαρμογές όχι μόνο στην θεωρία γραφημάτων αλλά και σε άλλους τομείς των μαθηματικών. Η κύρια συνεισφορά του ήταν στην απόδειξη ενός θεωρήματος για την ύπαρξη αριθμητικών προόδων σε υποσύνολα θετικής πυκνότητας. Η εργασία βασίζεται σε 3-4 paper με πιο σημαντικό αυτό του Timothy Gowers σχετικά με την ψευδοτυχαιότητα σε υπερ-γραφήματα.