MS Thesis colloquium

Title: Random graphs with given degree sequence
Speaker: Neeladri Maitra (IISc Mathematics)
Date: 24 September 2020
Time: 2:30 pm
Venue: Microsoft Teams (online)

The first part of this talk deals with identifying and proving the scaling limit of a uniform tree with given child sequence. A non-negative sequence of integers $\mathbf{c}=(c_1, c_2, …, c_l)$ with sum $l-1$ is called a child sequence for a rooted tree $t$ on $l$ nodes, if for some ordering $v_1, v_2,…, v_l$ of the nodes, $v_i$ has exactly $c_i$ many children. Consider for each $n$, a child sequence $\mathbf{c}^n$ with sum $n-1$, and let $\mathbf{t}_n$ be the plane tree with $n$ nodes, which is uniformly distributed over the set of all plane trees having $\mathbf{c}^n$ as their child sequence. Broutin and Marckert (2012) prove that under certain assumptions on $\mathbf{c}^n$, the scaling limit of $\mathbf{t}_n$, suitably normalized, is the Brownian Continuum Random Tree (BCRT). We consider a more general setting, where a finite number of vertices of $\mathbf{t}_n$ are allowed to have large degrees. We prove that the scaling limit of $\mathbf{t}_n$ in this regime is the Inhomogeneous Continuum Random Tree (ICRT), in the Gromov-Hausdorff sense.

In the second part, we look at vacant sets left by random walks on random graphs via simulations. Cerny, Teixeira and Windisch (2011) proved that for random $d$-regular graphs, there is a number $u_{\star}$, such that if a random walk is run up to time $un$ with $u<u_{\star}$, $n$ being the total number of nodes in the graph, a giant component of size $\text{O}(n)$ of the subgraph spanned by the vacant nodes i.e. the nodes that are not visited by the random walk, is seen. Whereas if the random walk is run up to time $un$ with $u>u_{\star}$, the size of the largest component of the subgraph spanned by the vacant nodes becomes $\text{o}(n)$. With the help of simulations, we try to investigate whether there is such a phenomenon for supercritical configuration models with heavy-tailed degrees.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 04 Dec 2020