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 language | English |
---|---|
Qualification | PhD |
Awarding Institution |
|
Supervisors/Advisors |
|
Award date | 19 Feb 2025 |
DOIs | |
Publication status | Published - 19 Feb 2025 |
Keywords
- networks
- graph theory
- graph
- dynamics
- combinatorics
- random
- probability
- limits