Εισαγωγή στα τυχαία d-κανονικά γραφήματα

Ιάσονας Προδρομίδης (Princeton)

Περίληψη: Στην ομιλία αυτή, θα μιλήσουμε για τη δομή που έχει ένα τυχαίο d-κανονικό γράφημα. Ξεκινούμε εισάγοντας τον τρόπο με τον οποίο κατασκευάζονται. Αντλούμε χρήσιμα συμπεράσματα για τη δομή του γραφήματος, όπως τη συνεκτικότητα ή τον αριθμό των μικρών κύκλων που περιέχει. Αν υπάρχει χρόνος, θα συζητηθεί και η μέθοδος δέσμευσης μικρών υπογραφημάτων (small subgraph conditioning method), μία από τις κύριες του κλαδου όσον αφορά την εύρεση ποσοτήτων που αφορούν ένα τυχαίο d-κανονικό γράφημα.

Abstract: In this talk, we will talk about the structure of a random d-regular graph. We start by introducing how they are constructed. We draw useful conclusions about the structure of the graph, such as its connectivity or the number of small cycles it contains. If there is time, we will also discuss the small subgraph conditioning method, one of the main ones in the field when it comes to finding quantities related to a random d-regular graph.