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).

Structural combinatorics

There are some very subtle combinatorial patterns and surprising theorems.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Design theory

A simple result in this area of combinatorics is that the problem of forming sets, described in the introduction, has a solution only if n has the form q2 + q + 1. It is less simple to prove that a solution exists if q is a prime power, may exist if q is a sum of two square numbers, but cannot exist for any other positive integer q. This last result, the Bruck-Ryser theorem, is proved by a combination of constructive methods based on finite fields and an application of quadratic forms.

Related Topics:
Prime power - Square numbers - Bruck-Ryser theorem - Finite field - Quadratic form

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

When such a structure does exist, it is called a finite projective plane; thus showing how finite geometry and combinatorics intersect.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Ramsey theory

Frank P. Ramsey proved that, given any group of six people, it is always the case that one can find three people out of this group that either all know each other, or all do not know each other.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The proof is a short proof by contradiction: suppose the claim is false. This means that we can have a group of six people such that whenever we look at any three of the six, there are at least two people among these three that know each other and at least two who do not know each other. Consider now one person among the six; call this person "A." Now, among the remaining five people, there must be at least three who either all know A or all do not know A--this is clear since the negation of one condition immediately implies the other condition. Assume first former condition: that at least three of the remaining five know A. Among those three people, at least two of them must know each other, since otherwise we would have three people who all don't know each other, contrary to our hypothesis. But then we have two people who know each other, and know A, and so these two people, along with A, constitute a group of three people among the six who all know each other. This contradicts our initial hypothesis. Assuming that other condition--that three of the remaining five do not know A--results in a similar contradiction.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This is a special case of Ramsey's theorem.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The idea of finding order in random configurations gives rise to Ramsey theory. Essentially this theory says that any sufficiently large configuration will contain at least one instance of some other type of configuration.

Related Topics:
Ramsey theory - Sufficiently large

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Matroid theory

This part of combinatorics abstracts part of geometry. It studies the properties of sets (usually, finite sets) of vectors in a vector space that do not depend on the particular coefficients in a linear dependence relation. Not only the structure but also enumerative properties belong to matroid theory.

Related Topics:
Geometry - Vector space - Linear dependence

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For instance, given a set of n vectors in Euclidean space, what is the largest number of planes they can generate? (Answer: the binomial coefficient C(n,3).) Is there a set that generates exactly one less plane? (No, in almost all cases.) These are extremal questions in geometry.

Related Topics:
Euclidean space - Plane - Binomial coefficient

~ ~ ~ ~ ~ ~ ~ ~ ~ ~