Uncovering a graph

• 成果类型: Article
• 署名作者: Janson, Svante
• 署名单位: Uppsala University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051; 1432-2064
• DOI: 10.1007/s00440-025-01401-9
• 发表日期: 2026-06
• 页码: 689-740
• 关键词: Random graphs; random trees; Random uncovering of vertices; branching-processes; trees

摘要

Uncover the vertices of a given graph, deterministic or random, in uniformly random order; we consider both a discrete-time and a continuous-time version. We study the evolution of the number of visible edges, and show convergence after normalization to a Gaussian process. This problem was studied by Hackl, Panholzer, and Wagner for the case when the graph is a uniformly random labelled tree; we generalize their result to more general graphs, including both other classes of random and non-random trees, and denser graphs. The results are similar in all cases, but some differences can be seen depending on the size of the average degree and of the variance of the vertex degrees.