 | This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(November 2024) (Learn how and when to remove this message) |
Extremal combinatorics is a field ofcombinatorics, which is itself a part ofmathematics. 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 concernsclasses of sets; this is calledextremal set theory. For instance, in ann-element set, what is the largest number ofk-elementsubsets that can pairwise intersect one another? What is the largest number of subsets of which none contains any other? The latter question is answered bySperner's theorem, which gave rise to much of extremal set theory.
Another kind of example: How many people can be invited 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 (seeTheorem on Friends and Strangers). 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.
.svg) | Thiscombinatorics-related article is astub. You can help Wikipedia byadding missing information. |