Merino
Le Jeudi 2 Mars 2000 à 14h30
au LRI, Salle 101
(Oxford)
The chip-firing game and the Tutte polynomial
Résumé/Abstract :
The chip firing game since its appearance has
been proved to be fruitful for different fields such as graph
theory, algebraic combinatorics, self-organized criticality and
statistical physics.
Most of the research on chip firing games on undirected and directed
graphs started as a way of analysing dynamic behaviour of processes
in other areas, like Markov chains and self-critical systems. Later,
Norman Biggs put a particular instance
of chip firing games in the context of algebraic graph theory and
showed its intrinsic relation with algebraic and combinatorial invariants
of graphs, such as the Picard group or the number of spanning trees of the
graph. Here we show that this chip firing game on graphs
is actually related with the algebraic and topological structure of
graphic matroids; specifically, with the Tutte polynomial of the
graph and the h-vector of the matroid complex of the graph.