PC Seminar: Uncovering a graph

Abstract: Let G be a graph, deterministic or random, and uncover its vertices one by one, in uniformly random order. This yields a growing sequence of (random) induced subgraphs of G, and we study the evolution of this sequence. More precisely, we study only the evolution of the number of edges in these subgraphs. 
This question (among others) was studied by Hackl, Panholzer and Wagner (AofA 2022) for the case when $G$ is a uniformly random labelled tree. They showed that the stochastic process given by the number of visible edges, after suitable rescaling, converges to a continuous Gaussian process, which resembles a Brownian bridge but with a somewhat different distribution. (The proof uses an exact formula for a multivariate generating function.) Our main result is that this result extends to a wide class of deterministic and random trees and graphs. 
The problem can be seen as dual to the random graph process introduced by Erdös and Renyi, where the edges of a complete graph are uncovered in random order. Our proof uses an adaption of a method introduced for that problem (Janson 1990, 1994). 
 

This is a seminar in our seminar series on Probability and Combinatorics (PC).