Extremal combinatorics: Difference between revisions

Revision as of 05:25, 14 September 2005

Revision as of 20:43, 15 September 2005

Line 1:

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

{{cleanup}}

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 don't know each other? 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 as large as possible subset 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.

Extremal combinatorics - a field of combinatorial mathematics which has undergone a period of spectacular growth in recent decades. The word "extremal" comes from the nature of problems this field deals with: if a collection of finite objects (numbers, graphs, vectors, sets, etc.) satisfies certain restrictions, how large or how small can it be?

==References==

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 don't know each other? An easy 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 as large as possible subset 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.

Source:* Stasys Jukna, ''Extremal Combinatorics, With Applications in Computer Science'' ([http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/EC_Book/preface.html preface]). Springer-Verlag, 2001. ISBN 3-540-66313-4.

{{math-stub}}