Skip to main content Skip to navigation

Enumerative Combinatorics

Given a class of objects, one simple question one can ask is: how many are there? Sometimes this question may be easy to answer: there are 2(n2-n)/2 graphs on n vertices. Sometimes it may be much harder: how many triangle-free graphs on n vertices are there? This question was answered asymptotically by Erdős, Kleitman and Rothschild, who showed that almost every triangle-free graph is in fact bipartite, and it is easy to enumerate the triangle-free graphs.

Usually in the process of enumerating a class of objects (whether exactly or asymptotically) one discovers that a typical object from the given class has certain properties (for example, a typical triangle-free graph is bipartite). This forms the basis for the study of random objects drawn from the class.

Sample publications: