Extremal and probabilistic results for order types

A configuration is a finite set of points in the plane. Two configurations A and B have the same order type if there exists a bijection between them preserving the orientation of every ordered triple. We investigate extremal and probabilistic problems related to configurations in general position. We focus on problems involving forbidden configurations or monotone/hereditary properties. Thus, we typically have a given configuration B and we consider the property of being “B-free”: a configuration A is B-free if no subset of points of A has the same order type as B. We prove a significant bound on the number of B-free N-point configurations contained in the m × m grid [m]² for arbitrary configurations B. We consider random N-point configurations U^N in the unit square, in which each of the N points is chosen uniformly at random and independently of all other points. The above-mentioned enumeration result for B-free configurations in the grid is then used to prove strong bounds for the probability that the random set U^N should be B-free for any given B. We also investigate the threshold function N₀ = N₀(n) for the property that U^N should be n-universal, that is, should contain all n-point configurations in general position. As it turns out, N₀ = N₀(n) is doubly exponential in n; we prove that log log N₀ = Θ(n). Our arguments are mostly geometric and combinatorial, with the recent container method playing an important role. Also important for us is how large a grid one needs to consider when representing n-point configurations in general position.