Combinatorics Seminar

When: Sunday, November 9, 10am
Where: Schreiber 309
Speaker: Felix Goldberg, Caesarea Rothschild Institute, University of Haifa
Title: Power laws, sandpiles and pseudo-inverses


Power laws Y=aX^b are ubiquitous, showing up is such disparate contexts as: frequencies of earthquakes as a function of magnitude (Gutenberg-Richter law; b=1); metabolism rates in animals as a function of mass (Kleiber's law, b=3/4), and the growth of cities (Gibrat's law, b=3/4).

The sandpile model is a simple mathematical model, proposed by physicist Per Bak, to model the emergence of power laws. In my talk I will discuss a fixed-energy variant, the so called chip-firing game, originally introduced by Bjorner, Lovasz and Shor (BLS) in 1991.

A number of chips are placed on graph's vertices and at every turn, the solitaire player chooses a vertex i of degree d, which has at least d_i chips on it and then "fires" i by shifting a chip from i to each of i's neighbors. BLS have proved the remarkable result that whenever the game terminates, it always does so in the same number of moves, irrespective of gameplay! (I will explain the background for this.) Upper bounds on the number of moves have been given by BLS, G. Tardos, and others. However, in practice the game usually ends in far fewer moves.

To explain this phenomenon, I will show a new approach to obtaining upper bounds which results in greatly improved bounds for some graph classes. For example, for the strongly regular graphs the standard O(nN) upper bounds can be improved by O(n+N). The technique involves the analysis of the graphs' discrete Laplacian.

No prior knowledge is assumed. As a bonus, I will show the "proof" that all but the tiniest animals must have lungs or gills.