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:

• D. Christofides. Induced lines in Hales-Jewett cubes Journal of Combinatorial Theory A, 114: 906 - 918, 2007.
  

• P. Allen, V.V. Lozin and M. Rao. Clique-width and the speed of hereditary properties Electronic Journal of Combinatorics, 16(1): R35, 2009.
  

• P. Allen. Forbidden induced bipartite graphs Journal of Graph Theory, 60: 219 - 241, 2009.
  

• P. Allen. Almost every 2-SAT function is unate. Israel Journal of Mathematics, 161: 311 - 346, 2007.