Extremal combinatorics: Difference between revisions

Revision as of 02:32, 23 February 2007

Revision as of 02:32, 23 February 2007

Line 1:

'''Extremal combinatorics''' is a field of [[combinatorics]], which is itself a part of [[mathematics]]. ExtremalExtremale combinatorics study how large or how small collections of finite objects ([[number]]s, [[graph (mathematics)|graph]]s, [[vector space|vector]]s, [[set]]s, etc.) can be, if they have to satisfy certain restrictions.

For example, how many people can we invite to a party where among each three people there are two who know each other and two who do not? An easy [[Ramsey theory|Ramsey-type]] argument shows that at most five persons can attend such a party. Or, suppose we are given a finite set of nonzero integers, and are asked to mark an subset as large as possible of them under the restriction that the sum of any two marked integers cannot be marked. It appears that (independent of what the given integers actually are) we can always mark at least one-third of them.