Antal A. Járai: Research interests
General areas of interests
Mathematical models of statistical physics, critical phenomena,
self-organized criticality, mean-field behaviour
Specific areas of interest
PhD projects available
A number of PhD projects are available related to the Abelian sandpile model,
that is described below.
Abelian sandpile model.
Let G be a finite connected graph with a distinguished vertex s, called the "sink".
We denote the set of vertices that are different from s by V and by E the
set of edges. A sandpile on G is an assignment of indistinguishable
particles to the vertices in V, specified by a map η : V → {0,1,2,...}.
If the vertex x has at least as many particles as its degree, that
is, η(x) ≥ deg(x), then x is allowed to topple, which means
that x sends one particle to each of its neighbours. Note that we do not keep
track of particles reaching the sink. The sandpile η is called stable,
if no vertex can topple, that is η(x) < deg(x) for all x ∈ V.
It is easy to see (using that G is connected) that any sandpile can be
stablized in finitely many steps, by carrying out possible topplings
in some order. It can also be shown that the final stable configuration
does not depend on what sequence of topplings was used [Dh90].
This is the reason the model is called "Abelian". We define a Markov chain
on the set of stable sandpiles as follows. At time step n, we add a
particle at a vertex in V chosen uniformly at random, and stabilize,
if necessary. It can be shown that there is a unique recurrent class,
and that the stationary distribution ν(G) is uniformly distributed
on the set of recurrent states [Dh90].
The set of recurrent states, denoted R(G), forms an
Abelian group, called the sandpile group of G [Dh90].
The group operation is as follows: given two recurrent
sandpiles η, ξ ∈ R(G), we form the
sandpile η + ξ (adding componentwise), and then
stabilize, to arrive at a new recurrent sandpile. The sandpile group is
isomorphic to a factor of the free Abelian group of rank |V|,
by the sublattice spanned by the integer row span of a matrix
Δ. This matrix Δ is the graph Laplacian on V:
Δ(x,y) = deg(x), if x = y; Δ(x,y) = -1,
if x is a neighbour of y; and Δ(x,y) = 0 otherwise.
A fascinating feature of the Abelian sandpile model is the
behaviour of its avalanches. When we add a new particle
in the sandpile Markov chain described above, the sequence
of topplings created in stablizing is called an avalanche.
Computer simulations (that are not difficult to write) show that
the sizes of avalanches range from very small (affecting none or
only a few vertices) to very large (affecting almost all vertices).
On the other hand, it is a difficult
problem in general to prove theorems making such statements
quantitative. See [LP10] for some fascinating questions about
sandpiles.
Project 1: Mixing times. How long does it take for the
sandpile Markov chain to reach its stationary distribution?
How does this depend on the size of the graph? The tools
available for this are the decomposition of the sandpile
group into a product of cyclic groups and discrete
Fourier analysis on Abelian groups.
Project 2: Effect of boundary conditions.
Let V be a finite subset of the d-dimensional integer
lattice. Form the wired graph G(V) by adding a sink s to V,
in such a way that s is linked to each vertex x on the boundary
of V by as many edges as the number of neighbours of
x in the complement of V. It can be shown that the stationary
distribution ν(G(V)) has a weak limit as V increases
to the entire lattice [AJ04]. What happens if a
fixed configuration of particles is imposed outside V?
That is, suppose we condition ν to agree with a fixed
particle configuration ξ in part of the complement of V.
Does this have a significant effect on the limit
as V increases to the entire lattice?
Useful tools for the above problem will be a bijection
between recurrent sandpiles on G and spanning trees of G
[MD91], as well as an algorithm of D.B. Wilson that
generates a spanning tree of G uniformly at random [Wi96].
Wilson's method gives a beautiful construction of
a random spanning tree from Loop Erased Random Walk.
This is defined as follows. Consider simple random walk on
the graph G started at a vertex x and stopped when the vertex
y is first hit. Following the
path of the random walk, chronologically erase any loop created:
that is, the first time when some vertex has been visited for the
second time, erase the loop that was created, and continue the
walk. The path with the loops erased is Loop Erased Random Walk
[La99], [LP].
Project 3: Zero dissipation limit.
Let V be a finite subset of the d-dimensional integer
lattice. Modify the sandpile model to allow continuous
height variables η(x) ∈ [0,∞). Let
γ > 0 be a real parameter. Call a
sandpile stable, if η(x) ∈ [0, 2d + &gamma).
If &eta(x) ≥ 2d + γ, x is allowed to topple,
which means that it sends unit height to each of its neighbours
and sends height γ to the sink. In other
words, the height of x is reduced by 2d + γ, the
height of each neighbour is increased by 1, and amount γ
is lost (dissipated). As γ → 0, the discrete
sandpile model is recovered [JRS11]. The rate of convergence
was estimated in [AJ11] in dimensions d = 2 and 3.
The goal of the project is to handle other dimensions.
Useful tools for this problem will be a bijection
between recurrent sandpiles on G and spanning trees of G
[MD92], as well as Wilson's algorithm described under Project 2.
Input from the preprint [JW11] will also be useful.
References
[AJ04] Athreya, S.R. and Járai, A.A.:
Infinite volume limit for the stationary distribution
of Abelian sandpile models.
Comm. Math. Phys.
249 197-213 (2004).
[Dh90] Dhar, D.:
Self-organized critical state of sandpile automaton models.
Phys. Rev. Lett.
64 1613-1616 (1990).
[J11] Járai, A.A.:
Rate of convergence estimates for the zero-dissipation limit
in Abelian sandpiles.
Preprint (2011).
arXiv:1101.1437v2
[JRS11] Járai, A.A., Redig, F. and Saada, E.:
Zero dissipation limit in the abelian avalanche model.
Preprint (2011).
arXiv:0906.3128v3
[JW11] Járai, A.A. and Werning, N.:
Minimal configurations and sandpile measures.
Preprint (2011).
arXiv:1110.4523v1
[La99] Lawler, G.F.:
Loop-erased random walk. In Perplexing problems in probability,
197-217, Progr. Probab., 44, Birkhäuser Boston, Boston, MA (1999).
[LP10] Levine, L. and Propp, J.:
What is ... a sandpile?
Notices Amer. Math. Soc.
57, no. 8, 976-979 (2010).
[LP] Lyons, R. and Peres, Y.:
Probability on trees and networks.
Book
in preparation.
[MD92] Majumdar, S.N. and Dhar, D.:
Equivalence between the Abelian sandpile model and the
q → 0 limit of the Potts model.
Phys. A
185, 129-145 (1992).
[Wi96] Wilson, D.B.:
Generating random spanning trees more quickly than the
cover time.
Proceedings
of the twenty-eighth annual ACM Symposium
on Theory of computing., ACM, New York,
269-303 (1996).
Research Interests |
Publications and Preprints
Home |
Department of Mathematical Sciences
|