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.