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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
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 MSC: 05D99 (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)