A large deviation method to compute the asymptotic number of sparse labelled multi-type connected graphs

The scope of this thesis is to present a probabilistic method, based on a large deviation principle, to compute the number of sparse, labelled, connected multi-type graphs. This combinatorial quantity is known in the literature for the single-type graph across different regimes, beyond the sparse case. However, the standard techniques used in the single-type setting do not extend naturally to the multi-type case, and the corresponding result for the multi-type graph has not yet been established. The approach used leads to an overview of random graphs, from the Erdős-Rényi model to the inhomogeneous random graph model. We study the main properties of the two, including their phase transition at the critical point and the probability of being fully connected. We observe that there is a typical edge configuration for a connected inhomogeneous random graph and use this result to determine the interesting combinatorial quantity. Finally, we show that our result is fundamental for the estimation of probabilities of connectedness in regimes in which the size of the graph $n$ and the edge probability $p$ are such that $\lim_{n\to \infty}np=0$. These regimes are particularly interesting for a deeper analysis of the inhomogeneous random graph, especially in the characterization of the large deviation behaviour of connected components of mesoscopic size, that emerge with nonzero probability in the critical window.

Lo scopo di questa tesi è presentare un metodo probabilistico, basato su un principio di grandi deviazioni, per calcolare il numero di grafi multi-tipo sparsi, etichettati e connessi. Questa quantità combinatoria è nota in letteratura per il grafo classico in diversi regimi, anche oltre il caso sparso. Tuttavia, le tecniche standard utilizzate non possono estendersi al caso multi-tipo, per cui la stessa quantità combinatoria per il grafo multi-tipo non è ancora stata determinata. L’approccio adottato prevede una panoramica generale sui grafi aleatori, dal modello di \ER a quello del grafo aleatorio inomogeneo. Vengono studiate le proprietà principali di entrambi, includendo la loro transizione di fase nel punto critico e la probabilità di connessione. Si osserva che esiste una configurazione tipica degli archi per un grafo inomogeneo connesso e si utlizza questo risultato per determinare la quantità combinatoria di interesse. Infine, mostriamo che il nostro risultato è fondamentale per opportune stime di probabilità di connessione in regimi in cui la dimensione del grafo $n$ e la probabilità di un arco $p$ è tale che $\lim_{n\to \infty}np = 0$. Questi regimi sono particolarmente interessanti per un analisi più approfondita del grafo aleatorio multi-tipo, specialmente nella caratterizzazione del comportamento a grandi deviazioni delle componenti connesse di dimensione mesoscopica, che emergono con probabilità non nulla nella finestra critica.