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
Abstract:
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.