PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] tight (Definition)

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) \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 Erdos-Szekeres theorem, $g(n)$ is always finite, so $g$ is a well-defined function.) The bounds for $g$ due to Erdos 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 Erdos-Szekeres conjecture, the formula for $g(n)$ is exactly the lower bound: $g(n) = 2^{n-2} + 1$ .




Anyone with an account can edit this entry. Please help improve it!

"tight" is owned by mps.
(view preamble | get metadata)

View style:

Also defines:  slack

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: formula, conjecture, upper bound, lower bound, well-defined, convex, contains, points, number, convex subset, function, general position, subsets, finite, collection
There are 10 references to this entry.

This is version 3 of tight, born on 2007-04-17, modified 2007-04-17.
Object id is 9207, canonical name is Tight.
Accessed 2061 times total.

Classification:
AMS MSC05D99 (Combinatorics :: Extremal combinatorics :: Miscellaneous)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)