School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA. E-mail: Mrazborov@math.ias.edu
Steklov Mathematical Institute, Moscow, Russia. E-mail: Mrazborov@math.ias.edu
Asymptotic extremal combinatorics deals with questions that in the language of model theory can be re-stated as follows. For finite models M, N of an universal theory without constants and function symbols (like graphs, digraphs or hypergraphs), let p(M, N) be the probability that a randomly chosen sub-model of N with ∣M∣ elements is isomorphic to M. Which asymptotic relations exist between the quantities p(M 1,N),…, p(M h,N), where M 1,…, M 1, are fixed “template” models and ∣N∣ grows to infinity?
In this paper we develop a formal calculus that captures many standard arguments in the area, both previously known and apparently new. We give the first application of this formalism by presenting a new simple proof of a result by Fisher about the minimal possible density of triangles in a graph with given edge density.
(Received July 05 2006)