PlanetMath (more info)
 Math for the people, by the people.
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,

$\displaystyle w(S) = \max \{ \vert T\vert \colon T\subset S$ and $ T$ is convex$\displaystyle \}. $
The function $ g$ is defined by
$\displaystyle g(n) = \min \{ \vert S\vert \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 Erdős-Szekeres theorem, $ g(n)$ is always finite, so $ g$ is a well-defined function.) The bounds for $ g$ due to Erdős and Szekeres are
$\displaystyle 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ős-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)

View style:

Also defines:  slack

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

Cross-references: conjecture, upper bound, lower bound, well-defined, convex, contains, points, convex subset, function, general position, subsets, finite, collection
There are 9 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 879 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)