[Colloquium] Theory Seminar Lunch this Thurs. 12:15 at TTI

[meridel]

THEORY SEMINAR LUNCH
 
Speaker: Evelina Toumpakari 
University of Chicago Math graduate student
 
Title: On the Abelian Sandpile model
Time: Thursday, October 14th 12:15pm 
Place: TTI-C (1427 E. 60th St., 2nd Floor) 
LUNCH PROVIDED 
 
Abstract: Motivated by statistical physics (self-organized criticality),
the abelian sandpile automaton is a variant of the chip-firing game
studied by Bjorner, Lovasz, Shor, E. Tardos, G. Tardos, and others. We
take a rooted directed graph X in which the root is accessible from
every vertex. Every ordinary (non-root) vertex has an associated pile of
identical grains. When the height h(i) of the pile at an ordinary vertex
i reaches its outdegree deg(i), the vertex i "topples," i.e., passes
deg(i) grains to its out-neighbors, one along each outgoing edge. Grains
passed to the root disappear; therefore, every toppling sequence
("avalanche") is finite. A state is "stable" if h(i) < deg(i) for each
ordinary vertex i.

Lovasz at al showed that the stable state reached after an avalanche
depends solely on the initial state. This permits to define addition on
the set S of stable states, by adding pointwise and toppling. States
reachable from every state are called recurrent. (S,+) is a commutative
semigroup; the recurrent states form a subgroup G, the "sandpile group"
of X (Dhar, 1990). The order of G is the number of directed spanning
trees oriented toward the root; this is also the determinant of the
truncated Laplacian of X. The defining relations of G correspond to the
rows of the truncated Laplacian.

We study combinatorial, algebraic, and algorithmic aspects of this
model. We relate the structure of S to the structure of X. We consider a
number of related algorithmic questions, several of which have an
unresolved complexity status. We describe the structure of G in detail
for the case when X is a ball in a regular tree plus a root connected to
the leaves.

Some of the results are joint work with Laszlo Babai.
The speaker's advisor is Steven Lalley.
 
If you have questions, please contact Meridel at 4-9873 or
mtrimble at tti-c.org
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20041011/534d8cc9/attachment.htm