tight
Tight
2007-04-17 16:24:38
2007-04-17 20:40:44
Definition
upper bound
slack
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
A bound is \emph{tight} if it can be realized. A bound that is not
tight is sometimes said to be \emph{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) \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
\PMlinkname{Erd\H{o}s-Szekeres theorem}{HappyEndingProblem}, $g(n)$ is
always finite, so $g$ is a well-defined function.) The bounds for $g$
due to Erd\H{o}s and Szekeres are
\[
2^{n-2} + 1\le g(n) \le \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\H{o}s-Szekeres conjecture, the formula for $g(n)$
is exactly the lower bound: $g(n) = 2^{n-2} + 1$.
\PMlinkescapeword{bound}
\PMlinkescapeword{bounds}
\PMlinkescapeword{size}
\PMlinkescapeword{weight}