The Abelian Sandpile Model, studied in statistical physics, computer science, and graph theory, associates algebraic structures with a rooted directed multigraph X in which the root is accessible from every vertex, as follows. For vertices i, j, let aij denote the number of i → j edges and let deg(i) denote the out-degree of i. Let V be the set of non-root vertices. With each i ∈ V associate a symbol xi and consider the relations deg( i)xi = j∈V aijxj. Let M,S , and G be the commutative monoid, semigroup and group, respectively, generated by {lcub}xi : i ∈ V{rcub} subject to these relations. M is the sandpile monoid, S is the sandpile semigroup, and G is the sandpile group of X . The sandpile group has been the subject of extensive study for various special classes of graphs, including the square lattice and the n -dimensional cube.; The main results of the thesis cover two areas: (1) a general study of the connections between the algebraic structure of M,S, G , and the combinatorial structure of the underlying digraph X ; (2) a detailed analysis of the structure of the sandpile groups G(d, h) for a special class of graphs T (d, h), the complete d-regular trees of radius h with a root attached (d - 1)-fold to each leaf.; Ad (1), the universal lattice of M turns out to be distributive and is characterized via the strong components of X .; If the idempotent in S is unique (this includes the important case when the digraph without the root is strongly connected), then the Rees quotient S/G (obtained by contracting G to a zero element) is nilpotent; let k denote its class. We establish the existence of functions psi1 and psi 2 such that | S/G | psi1(k) and G contains a cyclic subgroup of index ≤psi2( k). This result follows from our asymptotic characterization of X as a "circular tollway system of bounded effective volume."; Ad (2), we compute the rank, exponent, order, and other structural parameters of the sandpile group G = G(d, h). We find a cyclic Hall-subgroup of order (d - 1) h. We prove that the rank of G is ( d - 1)h and G contains a subgroup isomorphic to Zd-1 hd . We find that the base-(d - 1) logarithm of the exponent and of the order are asymptotically 3h 2/pi2 and cd( d - 1)h, respectively.
展开▼
