# 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\colon\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)=\max\{|T|\colon T\subset S\text{\ and T is convex}\}.$

The function $g$ is defined by

 $g(n)=\min\{|S|\colon w(S)\geq 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\leq g(n)\leq\binom{2n-4}{n-2}+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 Tight 2013-03-22 16:56:23 2013-03-22 16:56:23 mps (409) mps (409) 6 mps (409) Definition msc 05D99 slack