| Version 2 |
Version 1 |
| A bound is \emph{tight} if it can be realized. A bound that is not |
A bound is \emph{tight} if it can be realized. A bound that is not |
| tight is sometimes said to be \emph{slack}. |
tight is sometimes said to be \emph{slack}. |
|
|
| For example, let $\mathcal{S}$ be the collection of all finite subsets |
For example, let $\mathcal{S}$ be the collection of all finite subsets |
| of $\mathbb{R}^2$ in general position. Define a function |
of $\mathbb{R}^2$ in general position. Define a function |
| $g\colon\mathbb{N}\to\mathbb{N}$ as follows. First, let the weight of |
$g\colon\mathbb{N}\to\mathbb{N}$ as follows. First, let the weight of |
| an element of $\mathcal{S}$ be the size of its largest convex subset, |
an element of $\mathcal{S}$ be the size of its largest convex subset, |
| that is, |
that is, |
| \[ |
\[ |
| w(S) = \max \{ |T| \colon T\subset S\text{\ and $T$ is convex} \}. |
w(S) = \max \{ |T| \colon T\subset S\text{\ and $T$ is convex} \}. |
| \] |
\] |
| The function $g$ is defined by |
The function $g$ is defined by |
| \[ |
\[ |
| g(n) = \min_{S\in w^{-1}(n)} |S|, |
g(n) = \min_{S\in w^{-1}(n)} |S|, |
| \] |
\] |
| that is, $g(n)$ is the smallest number such that any collection of |
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 |
$g(n)$ points in general position contains a convex $n$-gon. (By the |
| \PMlinkname{Erd\H{o}s-Szekeres theorem}{HappyEndingProblem}, $g(n)$ is |
Erd\H{o}s-Szekeres theorem, $g(n)$ is always finite, so $g$ is a |
| always finite, so $g$ is a well-defined function.) The bounds for $g$ |
well-defined function.) The bounds for $g$ due to Erd\H{o}s and |
|
due to Erd\H{o}s and Szekeres are
|
Szekeres are |
| \[ |
\[ |
| 2^{n-2} + 1\le g(n) \le \binom{2n-4}{n-2} + 1. |
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 |
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. |
$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, |
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)$ |
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$. |
is exactly the lower bound: $g(n) = 2^{n-2} + 1$. |
|
|
| \PMlinkescapeword{bound} |
\PMlinkescapeword{bound} |
| \PMlinkescapeword{bounds} |
\PMlinkescapeword{bounds} |
| \PMlinkescapeword{size} |
\PMlinkescapeword{size} |
| \PMlinkescapeword{weight} |
\PMlinkescapeword{weight} |
