Title: A probabilistic approach to the leader problem in random graphs,
Abstract: Consider the classical Erdos-Renyi random graph process wherein one starts
with an empty graph on $n$ vertices at time $t=0$. At each stage, an edge is
chosen uniformly at random and placed in the graph. After the original
fundamental work in [19], Erdős suggested that one should view the original
random graph process as a "race of components". This suggested understanding
functionals such as the time for fixation of the identity of the maximal
component, sometimes referred to as the "leader problem". Using refined
combinatorial techniques, {\L}uczak [25] provided a complete analysis of this
question including the close relationship to the critical scaling window of the
Erdos-Renyi process. In this paper, we abstract this problem to the context of
the multiplicative coalescent which by the work of Aldous in [3] describes the
evolution of the Erdos-Renyi random graph in the critical regime. Further,
different entrance boundaries of this process have arisen in the study of heavy
tailed network models in the critical regime with degree exponent $\tau \in
(3,4)$. The leader problem in the context of the Erdos-Renyi random graph also
played an important role in the study of the scaling limit of the minimal
spanning tree on the complete graph [2]. In this paper we provide a
probabilistic analysis of the leader problem for the multiplicative coalescent
in the context of entrance boundaries of relevance to critical random graphs.
As a special case we recover {\L}uczak's result in [25] for the Erdos-Renyi
random graph.