tight


A bound is tight if it can be realized. A bound that is not tight is sometimes said to be slack.

For example, let 𝒮 be the collection of all finite subsets of 2 in general positionMathworldPlanetmath. Define a function g: as follows. First, let the weight of an element S of 𝒮 be the size of its largest convex subset, that is,

w(S)=max{|T|:TS and T is convex}.

The function g is defined by

g(n)=min{|S|:w(S)n},

that is, g(n) is the smallest number such that any collection of g(n) points in general position contains a convex n-gon. (By the Erdős-Szekeres theorem (http://planetmath.org/HappyEndingProblem), g(n) is always finite, so g is a well-defined function.) The bounds for g due to Erdős and Szekeres are

2n-2+1g(n)(2n-4n-2)+1.

The lower bound is tight because for each n, there is a set of 2n-2 points in general position which contains no convex n-gon. On the other hand, the upper bound is believed to be slack. In fact, according to the Erdős-Szekeres conjecture, the formula for g(n) is exactly the lower bound: g(n)=2n-2+1.

Title tight
Canonical name Tight
Date of creation 2013-03-22 16:56:23
Last modified on 2013-03-22 16:56:23
Owner mps (409)
Last modified by mps (409)
Numerical id 6
Author mps (409)
Entry type Definition
Classification msc 05D99
Defines slack