# 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 $\mathcal{S}$ be the collection of all finite subsets
of ${\mathbb{R}}^{2}$ in general position^{}. Define a function
$g:\mathbb{N}\to \mathbb{N}$ as follows. First, let the weight of
an element $S$ of $\mathcal{S}$ be the size of its largest convex subset,
that is,

$$w(S)=\mathrm{max}\{|T|:T\subset S\text{and}T\text{is convex}\}.$$ |

The function $g$ is defined by

$$g(n)=\mathrm{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 |