Λέσχη Μαθηματικών

Χειμερινό εξάμηνο 2025-26, Τμ. Μαθηματικών ΕΚΠΑ

30 10 Αίθουσα Α12 Ώρα 12:15	Connectedness on Random Graphs Κωστής Θεoτοκάτος Περίληψη: Σκοπός αυτής της ομιλίας είναι να κάνουμε μια εισαγωγή στα τυχαία γραφήματα και να εξετάσουμε την πιθανότητα με την οποία ένα γράφημα είναι συνεκτικό στο μοντέλο Erdős-Rényi. Σε αυτό το μοντέλο έχουμε δύο παραμέτρους, το πλήθος των κορυφών του γραφήματος \(n\) και ένα \(0 < p < 1\), το οποίο εν γένει εξαρτάται από το \(n\) και κατασκευάζουμε γραφήματα με την εξής διαδικασία: Για κάθε δύο διαφορετικές κορυφές, αυτές ενώνονται με ακμή με πιθανότητα \(p\) και κάθε ζεύγος κορυφών είναι ανεξάρτητο από τα υπόλοιπα ζεύγη. Όπως θα δούμε, η πιθανότητα ενός γραφήματος να είναι συνεκτικό, αλλάζει δραματικά καθώς αλλάζει η πιθανότητα \(p\). Συγκεκριμένα, θα δείξουμε ότι η: $$p(n) = \dfrac{\log n}{n}$$ είναι μια threshold function για τη συνεκτικότητα του γραφήματος, δηλαδή αν: $$\lim_{n \to \infty} \dfrac{p(n)}{\frac{\log n}{n}} = \infty$$ ισχύει ότι η πιθανότητα ένα γράφημα να είναι συνεκτικό τείνει στο \(1\) καθώς το \(n\) τείνει στο \(\infty\) και αν: $$\lim_{n \to \infty} \dfrac{p(n)}{\frac{\log n}{n}} = 0$$ τότε η πιθανότητα ένα γράφημα να είναι συνεκτικό τείνει στο \(0\) καθώς το \(n\) τείνει στο \(\infty\). Η ύπαρξη μιας τέτοιας συνάρτησης για μια ιδιότητα γραφημάτων είναι τυπική για "αύξουσες" ιδιότητες, δηλαδή ιδιότητες που διατηρούνται από ένα γράφημα αν προσθἐσουμε ακμές σε αυτό, όπως είναι η δηλαδή και η συνεκτικότητα. Abstract: The purpose of this talk is to give an introduction to random graphs and to examine the probability of a graph being connected in the Erdoss-Renyi model. In this model we have two parameters, the number of vertices of the graph \(n\) and a \(0 < p < 1\), which in general depends on \(n\) and we construct graphs according to the following procedure: For every two distinct vertices, they are joined by an edge with probability \(p\) and each pair of vertices is independent of the other pairs. As we will see, the probability of a graph being connected changes dramatically as the probability \(p\) changes. Specifically, we will show that: $$p(n) = \dfrac{\log n}{n}$$ is a threshold function for the connectedness of the graph, that is, if: $$\lim_{n \to \infty} \dfrac{p(n)}{\frac{\log n}{n}} = \infty$$ it holds that the probability of a graph being connected tends to \(1\) as \(n\) tends to \(\infty\) and if: $$\lim_{n \to \infty} \dfrac{p(n)}{\frac{\log n}{n}} = 0$$ then the probability of a graph being connected tends to \(0\) as \(n\) tends to \(\infty\). The existence of such a function for a graph property is typical for "increasing" properties, that is, properties that are preserved by a graph if we add edges to it, such as connectivity.

30
10

Αίθουσα Α12

Ώρα 12:15

Connectedness on Random Graphs

Κωστής Θεoτοκάτος

Περίληψη: Σκοπός αυτής της ομιλίας είναι να κάνουμε μια εισαγωγή στα τυχαία γραφήματα και να εξετάσουμε την πιθανότητα με την οποία ένα γράφημα είναι συνεκτικό στο μοντέλο Erdős-Rényi. Σε αυτό το μοντέλο έχουμε δύο παραμέτρους, το πλήθος των κορυφών του γραφήματος $n$ και ένα $0 < p < 1$, το οποίο εν γένει εξαρτάται από το $n$ και κατασκευάζουμε γραφήματα με την εξής διαδικασία: Για κάθε δύο διαφορετικές κορυφές, αυτές ενώνονται με ακμή με πιθανότητα $p$ και κάθε ζεύγος κορυφών είναι ανεξάρτητο από τα υπόλοιπα ζεύγη.

Όπως θα δούμε, η πιθανότητα ενός γραφήματος να είναι συνεκτικό, αλλάζει δραματικά καθώς αλλάζει η πιθανότητα $p$. Συγκεκριμένα, θα δείξουμε ότι η: $$p(n) = \dfrac{\log n}{n}$$ είναι μια threshold function για τη συνεκτικότητα του γραφήματος, δηλαδή αν: $$\lim_{n \to \infty} \dfrac{p(n)}{\frac{\log n}{n}} = \infty$$ ισχύει ότι η πιθανότητα ένα γράφημα να είναι συνεκτικό τείνει στο $1$ καθώς το $n$ τείνει στο $\infty$ και αν: $$\lim_{n \to \infty} \dfrac{p(n)}{\frac{\log n}{n}} = 0$$ τότε η πιθανότητα ένα γράφημα να είναι συνεκτικό τείνει στο $0$ καθώς το $n$ τείνει στο $\infty$. Η ύπαρξη μιας τέτοιας συνάρτησης για μια ιδιότητα γραφημάτων είναι τυπική για "αύξουσες" ιδιότητες, δηλαδή ιδιότητες που διατηρούνται από ένα γράφημα αν προσθἐσουμε ακμές σε αυτό, όπως είναι η δηλαδή και η συνεκτικότητα.

Abstract: The purpose of this talk is to give an introduction to random graphs and to examine the probability of a graph being connected in the Erdoss-Renyi model. In this model we have two parameters, the number of vertices of the graph $n$ and a $0 < p < 1$, which in general depends on $n$ and we construct graphs according to the following procedure: For every two distinct vertices, they are joined by an edge with probability $p$ and each pair of vertices is independent of the other pairs.

As we will see, the probability of a graph being connected changes dramatically as the probability $p$ changes. Specifically, we will show that: $$p(n) = \dfrac{\log n}{n}$$ is a threshold function for the connectedness of the graph, that is, if: $$\lim_{n \to \infty} \dfrac{p(n)}{\frac{\log n}{n}} = \infty$$ it holds that the probability of a graph being connected tends to $1$ as $n$ tends to $\infty$ and if: $$\lim_{n \to \infty} \dfrac{p(n)}{\frac{\log n}{n}} = 0$$ then the probability of a graph being connected tends to $0$ as $n$ tends to $\infty$. The existence of such a function for a graph property is typical for "increasing" properties, that is, properties that are preserved by a graph if we add edges to it, such as connectivity.