47 KAM Mathematical Colloquium
Prof. XAVIER G. VIENNOT
University of Bordeaux and LABRI
COMBINATORICS FOR QUANTUM GRAVITY
April 10, 2003
Lecture room in the 4th floor, Letenská 17, Praha 1
14:00 PM
Abstract
The relation between combinatorics and theoretical physics is
particularly active and fruitful. It is classical to relate statistical physics
and algebraic graph theory. In this lecture, I will introduce some recent
models for 2D quantum gravity which can be solved exactly using the
combinatorial theory of heaps of pieces.
Quantum gravity is a very active topic in theoretical physics. The purpose is
to unify two incompatible theories: general relativity and quantum mechanics.
Recently, physicists have introduced some discrete models in two dimensions,
called Lorentzian triangulations (Ambjorn, Loll, Di Francesco, Guitter,
Kristjansen). These models can be solved exactly, that is explicit expressions
for some physical quantities can be given. These quantities are in fact
generating functions for some enumeration problems.
I will show that the combinatorics involved is in fact the combinatorics of
heaps of pieces. This notion has been introduced by the author in order to give
a "geometric" and combinatorial interpretation of the algebraic notion of
commutation classes of words of the so-called Cartier-Foata monoids (called
trace monoids in theoretical computer science).
No prerequisites from physics or combinatorics are supposed.
Prof. Viennot will give on the next day, Friday April 11, in 11:00 AM in the same lecture
room the follow-up lecture
HEAPS OF PIECES IN PHYSICS
Abstract
The notion of "heaps of pieces" has been introduced by the author, as
a "geometrization" of the algebraic notion of commutation monoids defined by
Cartier and Foata. The theory has been developed by the Bordeaux group of
combinatorics, with strong interactions with statistical mechanics. In the
colloquium lecture I showed how heaps of pieces can be used for the resolution
of some models introduced recently by physicists for 2D Lorentzian quantum
gravity (Ambjorn, Loll and Di Francesco et al). In this seminar lecture, I will
go further in the theory of heaps of pieces and its various applications.
I begin by stating three basic lemma of the theory: an "inversion lemma"
giving generating functions of heaps as the quotient of two alternating
generating functions of "trivial" heaps, the "logarithmic lemma", and the "path
lemma" saying that any path can be put in bijection with a heap. Many results
and explicit formulae or identities in various papers scattered in the
combinatorics and physics literature can be unified and viewed as consequence
of these three basic lemma, once the translation of the problem into heaps
methodology has been made.
The first application is with the now classical directed animal models and gas
models with hard core interaction, such as Baxter's hard hexagons model.
Combinatorial interpretation of the density of the gas is given, relating the
model with directed animals (as given by Dhar,..).
A second topic is a unifying explanation of the appearance of some q-Bessel
functions in two lattice models: the staircase polygons (or parallelogram
polyominoes) (Bender, Delest, Fedou, ..) and the Solid-on-Solid model
(Owczarek, Prellberg,..).
A third application is in algebraic graph theory with the study of the zeroes
of the so-called matching polynomial of a graph.
