Add to Outlook calendar Add to Google calendar

MS Thesis defence

Title: Random graphs with given degree sequence
Speaker: Neeladri Maitra (IISc Mathematics)
Date: 14 June 2021
Time: 2 pm
Venue: Microsoft Teams (online)

In this talk, we focus on random graphs with a given degree sequence. In the first part, we look at uniformly chosen trees from the set of trees with a given child sequence. A non-negative sequence of integers $(c_1,c_2,\dots,c_l)$ with sum $l-1$ is a child sequence for a rooted tree $t$ on $l$ nodes, if for some ordering $v_1,v_2,\dots,v_l$ of the nodes of $t$, $v_i$ has exactly $c_i$ many children in $t$. We consider for each $n$, a child sequence $\mathbf{c}^{(n)}$, with sum $n-1$, and let $\mathbf{t}_n$ be the random tree having the uniform distribution on the set of all plane trees with $n$ vertices, which has $\mathbf{c}^{(n)}$ as their child sequence. Under the assumption that a finite number of vertices of $\mathbf{t}_n$ has large degrees, we show that the scaling limit of $\mathbf{t}_n$ is the Inhomogeneous Continuum Random Tree (ICRT), in the Gromov-Hausdorff topology. This generalizes a result of Broutin and Marckert from 2012, where they show the scaling limit to be the Brownian Continuum Random Tree (BCRT), under the assumption that no vertex in $\mathbf{t}_n$ has large degree.

In the second part, we look at vacant sets left by random walks on random graphs via simulations. CernĂ½, Teixeira and Windisch (2011) proved that for random $d$-regular graphs, there is a number $u_*$, such that if a random walk is run up to time $un$ with $u<u_*$, $n$ being the total number of nodes in the graph, a giant component of linear size, in the subgraph spanned by the nodes yet unvisited by the random walk, emerges. Whereas, if the random walk is tun up to time un with $u>u_*$, the size of the largest component, of the subgraph spanned by nodes yet unvisited by the walk, is $\text{o}(n)$. With the help of simulations, we try to look for such a phase transition 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: 30 Jul 2021