Book contents
- Frontmatter
- Contents
- Acknowledgments
- 1 A Happy Ending
- 2 Overview
- 3 Configurations
- 4 Subconfigurations
- 5 Properties, Parameters, and Obstacles
- 6 Computing with Configurations
- 7 Complexity Theory
- 8 Collinearity
- 9 General Position
- 10 General-Position Partitions
- 11 Convexity
- 12 More on Convexity
- 13 Integer Realizations
- 14 The Stretched Geometry of Permutations
- 15 Configurations from Graphs
- 16 Universality
- 17 Stabbing
- 18 The Big Picture
- Bibliography
- Index
5 - Properties, Parameters, and Obstacles
Published online by Cambridge University Press: 04 May 2018
- Frontmatter
- Contents
- Acknowledgments
- 1 A Happy Ending
- 2 Overview
- 3 Configurations
- 4 Subconfigurations
- 5 Properties, Parameters, and Obstacles
- 6 Computing with Configurations
- 7 Complexity Theory
- 8 Collinearity
- 9 General Position
- 10 General-Position Partitions
- 11 Convexity
- 12 More on Convexity
- 13 Integer Realizations
- 14 The Stretched Geometry of Permutations
- 15 Configurations from Graphs
- 16 Universality
- 17 Stabbing
- 18 The Big Picture
- Bibliography
- Index
Summary
With the notions of configurations and subconfigurations in hand, we are now ready to define monotone properties andmonotone parameters.
Definitions
Definition 5.1
We define a property of configurations to be something that is true of some configurations and false for others, but whose truth or falsity depends only on the configuration and not on the set of points that realizes it. A property is monotone if, whenever a configuration has the property, so do all its subconfigurations.
We have already discussed the monotonicity of the happy ending problem.
Example 5.2
Containing the vertices of a convex quadrilateral is not a monotone property, but not containing a convex quadrilateral ismonotone.
We may formalize a property either as a subset of the set of all configurations or as the characteristic function of this subset, a function of configurations that is true for the configurations with the property and false for the ones without it.
Definition 5.3
A parameter of configurations is a function from configurations to nonnegative integers. It is monotone if removing points from a configuration cannot cause the function value to increase.
Example 5.4
The size |S| of a configuration S is amonotone parameter, because all realizations of S have the same number of points, and because taking away points reduces the size.
We can also formproperties fromparameters.
Example 5.5
Whenever ρ is a monotone parameter of configurations, and k is a positive integer, then the property of a configuration S of having ρ(S) < k is a monotone property of configurations. For instance, the property of having size at most four is monotone.
Many classical problems in the discrete geometry of point sets can be formulated in terms of monotone properties and monotone parameters of configurations.
Obstacles
Every monotone property of configurations can be characterized by its obstacles, the smallest configurations that do not have the property.
Definition 5.6
If P is a monotone property of configurations, then the obstacles of P are the configurations that do not have P, but for which all proper subconfigurations do have P. P has bounded obstacles if there are finitely many obstacles for P.
- Type
- Chapter
- Information
- Forbidden Configurations in Discrete Geometry , pp. 24 - 32Publisher: Cambridge University PressPrint publication year: 2018