ART

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 (numbers, graphs, vectors, sets, etc.) can be, if it has to satisfy certain restrictions.

Much of extremal combinatorics concerns classes of sets; this is called extremal set theory. For instance, in an n-element set, what is the largest number of k-element subsets that can pairwise intersect one another? What is the largest number of subsets of which none contains any other? The latter question is answered by Sperner's theorem, which gave rise to much of extremal set theory.

Another kind of 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? Ramsey theory 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 as large a subset as possible of this set 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.

See also

Extremal graph theory
Sauer–Shelah lemma
Erdős–Ko–Rado theorem
Kruskal–Katona theorem
Fisher's inequality
Union-closed sets conjecture

References

Jukna, Stasys (2011), Extremal Combinatorics, With Applications in Computer Science, Birkhäuser Verlag, ISBN 3-540-66313-4.

Alon, Noga; Krivelevich, Michael (2006), Extremal and Probabilistic Combinatorics (PDF).

Frankl, Peter; Rödl, Vojtěch (1987), "Forbidden intersections", Transactions of the American Mathematical Society, 300 (1): 259–286, doi:10.2307/2000598.

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License