Increasing sequences of graphs are a powerful tool to describe empirical phenomena such as epidemics or friendships. When only a snapshot of the graph is accessible, we aim to estimate information about the past of the process, such as the order of appearance of vertices.
A graph is a collection of vertices connected by edges. We study sequences of growing graphs, that is, a sequence where vertices and edges are added one by one. There are many processes described by growing graphs, such as the world wide web. Here, websites are vertices and links from website A to B are edges. As new websites are created, new vertices and edges are added to the graph. We aim to get information about the past of the graph when only its current state is observed. This means, for example, deciding if the beginning of the process is forgotten over time or if it impacts the graph forever or to retrieve the first few vertices that were added to the graph.
Mathematicians have been interested in formalizing these questions on synthetic datasets. There, graphs are created from fixed attachment procedures, chosen to best resemble empirical examples. We are formalizing the problem of ordering all vertices in a graph, developing novel algorithms and advancing the theoretical understanding of said algorithms on synthetic data. To do so we must often study in details general properties of the graphs, producing results of independent interest.
