4 - Subconfigurations

Summary

How many sides can a convex polygon with vertices in a 5 × 5 grid have? To avoid spoiling this puzzle we defer the answer to Figure 11.3. Just as one set of points may be a subset of another, one configuration may be a subconfiguration of another. The puzzle seeks a polygon subconfiguration of grid(5, 5). We define subconfigurations more carefully in the rest of this chapter. In Chapter 5, we will use them to define monotone properties and parameters and to find obstacles, the subconfigurations that prevent a given configuration from having a property.

Definitions

Definition 4.1

A subconfiguration of a configuration S is any configuration that can be obtained from a realization of S by removing zero or more points. If T is a subconfiguration of S, an instance of T in S is a one-to-one matching of points in T to a subset of points in S so the matched points have the same orientations in T and in S. Each configuration is a subconfiguration of itself; T is a proper subconfiguration of S if it is a subconfiguration but unequal to S.

Example 4.2

Figure 4.1 shows all of the configurations on one to four points, with lines indicating pairs of subconfigurations that differ from each other by the addition or removal of a single point. In this diagram, one configuration is a subconfiguration of another if the two configurations are connected by a monotone path. For instance, the one-point configuration at the bottom of the diagram is a subconfiguration of all of the other configurations.

Note that the subconfigurations of a configuration T are not subsets of T, because T is not a set of points (it is an equivalence class of sets of points).

Partial Orders and Quasi-Orders

The subconfiguration relation between configurations forms an example of a partial order. This means that, if we write S→ T when S is a subconfiguration of T, then this relation →obeys the following three axioms:

• Reflexivity: For all configurations X, X → X.

• Anti-symmetry: For all configurations X and Y, if X _→Y and Y → X, then X = Y.

• Transitivity: For all configurations X, Y, and Z, if X →Y and Y → Z, then X → Z.