Dynamical Systems on Graphs

Research output: PhD ThesisPhD-Thesis - Research and graduation internal

120 Downloads (Pure)

Abstract

A group of people exchanging opinions. An artificial neural network making predictions. A virus spreading through a population. A brain retrieving a memory. A server allocating tasks to multiple computers. A power grid balancing supply and demand. A self-replicating machine in a cellular automaton. A random walk on the set of vertices of a graph. A random walk on the set of graphs with given number of vertices. Each of these phenomena can be viewed as a dynamical system on a graph, where vertices represent evolving quantities and edges represent interactions. This thesis concerns the relation between graph structure and dynamics. The first part of the thesis considers deterministic dynamics on finite graphs. For di!usive systems, we prove an upper bound on the dimension of the equilibrium set based on graph homology and a lower bound based on graph coverings. For the specific Kuramoto model, we solve a conjecture by constructing finite graphs with infinitely many stable equilibria, and classify nilpotent equilibria using Eulerian cycles. For general systems of equations with “a graph structure”, we show how solutions are controlled by subgraphs and apply the result to dynamical systems as well as spectral graph theory. The second part of the thesis concerns stochastic dynamics on finite graphs. More precisely, it considers occupancy processes, which include several interactive particle systems and random graph models as particular cases. We prove that finite-time deviations from typical behavior are controlled by the geometry of the graph as perceived by a random walker on the vertices. The third part of the thesis concerns dynamics on graph limits and their symmetries. Graph limits are describe the structure of graphs as the number of vertices grows to infinity. We prove that symmetries of graph limits lead to symmetries of their associated—typically infinite dimensional—dynamics, and use this fact to determine invariant patterns. Relations between graph structure and dynamics heavily depend on the specific evolution equations considered. Certain relations are model-specific, others vary between discrete and continuous time, and still others di!er between deterministic or stochastic dynamics. Yet, many of the ideas and tools developed for one class of graph dynamical systems often shed light on others.
Original languageEnglish
QualificationPhD
Awarding Institution
  • Vrije Universiteit Amsterdam
Supervisors/Advisors
  • Bick, Christian, Supervisor
  • Rink, Bob, Supervisor
Award date19 Feb 2025
DOIs
Publication statusPublished - 19 Feb 2025

Keywords

  • networks
  • graph theory
  • graph
  • dynamics
  • combinatorics
  • random
  • probability
  • limits

Fingerprint

Dive into the research topics of 'Dynamical Systems on Graphs'. Together they form a unique fingerprint.

Cite this