Asymptotic Enumeration Problems

This page is under development; eventually it will feature rather more material, as well as links to at least my own work on this subject.

For any kind of combinatorial structure, a fundamental and natural question is "How many of them are there (of given size n)?" Sometimes, there's an easy exact answer ("How many labelled graphs?", "How many trees?"). Sometimes one can express the exact answer indirectly using generating functions.

But sometimes this is too much to expect, and it is reasonable to aim for an approximate answer, probably only valid for large n. A classic result that I am particularly fond of is the Kleitman-Rothschild Theorem, which gives an approximation to the number of partially ordered sets with vertex set [n]. Moreover, it - perhaps inevitably - says something much more interesting, namely what "most" partially ordered sets look like.

Graham Brightwell

Last change: 9 September 2003