Dynamics on large locally tree-like graphs: a theory and some applications

Locally tree-like graphs are graphs with no or few short loops. A main example is Erdös-Renyi random graphs.Discrete-state dynamics on such graphs has many applications to epidemology, neuroscience, chemical kinetics and other fields. Two main general methods to analyze such systems are mean-field methods and direct numerical simulation. Both have advantages,but also draw-backs. For the special case of dynamics which obeys detailed balance and when one is looking for marginals of a steady state(marginals of a Gibbs-Boltzmann distribution) there exists a powerful alternative called the cavity method, or Belief Propagation. I will discuss a cavity approach to describe dynamics, with or without detailed balance. As an example I will discuss a localsearch heuristics to solve combinatorial optimization problems, that can be seen as a generalizations of simulated annealing whichdo not obey detailed balance. I will also discuss potential extensions to quantum dynamics on large locally tree-like graphs. The talk is based on joint work with Gino Del Ferraro, Eduardo Domínguez, David Machado and Roberto Mulet, partly published inPhys. Rev. E 95, 052119 (2017) and PRL vol 123:230602 (2019). Seminar held online. Zoom link https://us02web.zoom.us/j/233346745?pwd=aEtnb2pvdlZOdnYycm5XczVxb3EwUT09 Meeting ID: 233 346 745 Password: 032420