Combinatorics

Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. In particular, it is concerned with "counting" the objects in those collections (enumerative combinatorics), with deciding when the criteria can be met and then constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), with finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and with finding algebraic structures these objects may have (algebraic combinatorics).

Extremal combinatorics

Many extremal questions deal with set systems. A simple example is the following: what is the largest number of subsets of an n-element set one can have, if no two of the subsets are disjoint? Answer: half the total number of subsets. Proof: Call the n-element set S. Between any subset T and its complement S − T, at most one can be chosen. This proves the maximum number of chosen subsets is not greater than half the number of subsets. To show one can attain half the number, pick one element x of S and choose all the subsets that contain x.

Related Topics:
Set system - Complement

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A more difficult problem is to characterize the extremal solutions; in this case, to show that no other choice of subsets can attain the maximum number while satisfying the requirement.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~