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 position. Define a function $g:\mathbb{N}\to \mathbb{N}$ 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|:T\subset S\text{ and }T\text{ is convex}\}.$$

The function $g$ is defined by

$$g(n)=\min \{|S|:w(S)\ge 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

$$2^{n-2}+1\le g(n)\le \left(\genfrac{}{}{0pt}{}{2n-4}{n-2}\right)+1.$$

The lower bound is tight because for each $n$, there is a set of $2^{n-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)=2^{n-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