Enumeration and asymptotics of random walks and maps

47 mins 40 secs, 176.42 MB, iPod Video 480x360, 25.0 fps, 44100 Hz, 505.32 kbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/977/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Banderier, C (Paris 13) Friday 11 April 2008, 15:30-16:15 Combinatorial Identities and their Applications in Statistical Mechanics

Created:

2008-04-28 08:27

Collection:

Combinatorics and Statistical Mechanics

Publisher:

Isaac Newton Institute

Banderier, C

Language:

eng (English)

Credits:

Author:

Banderier, C


Abstract:	In this talk, I want to give a brief survey of what I did in analytic combinatorics (=using generating functions to enumerate combinatorial structures, and then using complex analysis to get the asymptotics). This survey will be based on 3 kinds of equations which are often met in combinatorics, the way we solve them, and what kind of generic methods we use to get the full asymptotics/limit laws. By full asymptotics, I mean an expansion like $$f_n \sim C A^n n^\alpha + C' A^n n^(\alpha-1) + C'' A^n n^(\alpha-2) + \dots$$ where $A$ is the growing rate and $\alpha$ the "critical exponent" of the corresponding combinatorial structure. Namely, I will show that three combinatorial structures are "exactly solvable" : - a directed random walk model (using the kernel method and singularity analysis of algebraic functions), - random walks on the honeycomb Lattice (using an Ansatz and Frobenius method for D-finite functions), - question of connectivity in planar maps (using Lagrange inversion and coalescing saddle points, leading to a ubiquitous distribution involving the Airy function). This talk is based on an old work with Philippe Flajolet, Michèle Soria, and Gilles Schaeffer, and on work in progress with Bernhard Gittenberger.

Abstract:

In this talk, I want to give a brief survey of what I did in analytic combinatorics (=using generating functions to enumerate combinatorial structures, and then using complex analysis to get the asymptotics).

This survey will be based on 3 kinds of equations which are often met in combinatorics, the way we solve them, and what kind of generic methods we use to get the full asymptotics/limit laws.

By full asymptotics, I mean an expansion like $$f_n \sim C A^n n^\alpha + C' A^n n^(\alpha-1) + C'' A^n n^(\alpha-2) + \dots$$ where $A$ is the growing rate and $\alpha$ the "critical exponent" of the corresponding combinatorial structure.

Namely, I will show that three combinatorial structures are "exactly solvable" : - a directed random walk model (using the kernel method and singularity analysis of algebraic functions),

- random walks on the honeycomb Lattice (using an Ansatz and Frobenius method for D-finite functions),

- question of connectivity in planar maps (using Lagrange inversion and coalescing saddle points, leading to a ubiquitous distribution involving the Airy function).

This talk is based on an old work with Philippe Flajolet, Michèle Soria, and Gilles Schaeffer, and on work in progress with Bernhard Gittenberger.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	480x360	1.84 Mbits/sec	657.88 MB	View	Download
WebM	480x360	692.2 kbits/sec	241.24 MB	View	Download
Flash Video	480x360	805.93 kbits/sec	281.37 MB	View	Download
iPod Video *	480x360	505.32 kbits/sec	176.42 MB	View	Download
QuickTime	384x288	848.58 kbits/sec	296.26 MB	View	Download
MP3	44100 Hz	125.02 kbits/sec	43.44 MB	Listen	Download
Windows Media Video		477.64 kbits/sec	166.76 MB	View	Download
Auto	(Allows browser to choose a format it supports)