In this discussion we consider load balancing on a large graph. Each edge has a unit of load that it wishes to distribute between its nodes in the most balanced way. For infinite graphs the corresponding load balancing problem exhibits nonuniqueness, related with role of boundary conditions in statistical mechanical models.
Nevertheless, we are able to extend the notion of balanced loads from large, finite graphs to their local weak limits, using the concept of unimodularity. The result applies in particular to the Erdös-Rényi model, where it settles a conjecture of Hajek (1990). Our proof is a new illustration of the objective method described by Aldous and Steele (2004).
All the necessary background from the machinery of local weak convergence that is needed will be developed during the talk. This machinery provides a way to study many problems of applied interest in large networks beyond just the load balancing problem that will be the focus of this talk. It is therefore valuable to familiarize oneself with this theory if one is interested in understanding the behavior of large networks such as wired and wireless networks, transportation networks, and social networks.
This research represents a joint work with Justin Salez from the Université Paris Diderot.