Enumerative combinatorics s on three
vertices, an example of
Catalan numbers. Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. Although counting the number of elements in a set is a rather broad
mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description.
Fibonacci numbers is the basic example of a problem in enumerative combinatorics. The
twelvefold way provides a unified framework for counting
permutations,
combinations and
partitions.
Analytic combinatorics Analytic combinatorics concerns the enumeration of combinatorial structures using tools from
complex analysis and
probability theory. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and
generating functions to describe the results, analytic combinatorics aims at obtaining
asymptotic formulae.
Partition theory . Partition theory studies various enumeration and asymptotic problems related to
integer partitions, and is closely related to
q-series,
special functions and
orthogonal polynomials. Originally a part of
number theory and
analysis, it is now considered a part of combinatorics or an independent field. It incorporates the
bijective approach and various tools in analysis and
analytic number theory and has connections with
statistical mechanics. Partitions can be graphically visualized with
Young diagrams or
Ferrers diagrams. They occur in a number of branches of
mathematics and
physics, including the study of
symmetric polynomials and of the
symmetric group and in
group representation theory in general.
Graph theory . Graphs are fundamental objects in combinatorics. Considerations of graph theory range from enumeration (e.g., the number of graphs on
n vertices with
k edges) to existing structures (e.g., Hamiltonian cycles) to algebraic representations (e.g., given a graph
G and two numbers
x and
y, does the
Tutte polynomial TG(
x,
y) have a combinatorial interpretation?). Although there are very strong connections between graph theory and combinatorics, they are sometimes thought of as separate subjects. While combinatorial methods apply to many graph theory problems, the two disciplines are generally used to seek solutions to different types of problems.
Design theory Design theory is a study of
combinatorial designs, which are collections of subsets with certain
intersection properties.
Block designs are combinatorial designs of a special type. This area is one of the oldest parts of combinatorics, such as in
Kirkman's schoolgirl problem proposed in 1850. The solution of the problem is a special case of a
Steiner system, which play an important role in the
classification of finite simple groups. The area has further connections to
coding theory and geometric combinatorics. Combinatorial design theory can be applied to the area of
design of experiments. Some of the basic theory of combinatorial designs originated in the statistician
Ronald Fisher's work on the design of biological experiments. Modern applications are also found in a wide gamut of areas including
finite geometry,
tournament scheduling,
lotteries,
mathematical chemistry,
mathematical biology,
algorithm design and analysis,
networking,
group testing and
cryptography.
Finite geometry Finite geometry is the study of
geometric systems having only a finite number of points. Structures analogous to those found in continuous geometries (
Euclidean plane,
real projective space, etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for
design theory. It should not be confused with discrete geometry (
combinatorial geometry).
Order theory of the
powerset of {x,y,z} ordered by
inclusion. Order theory is the study of
partially ordered sets, both finite and infinite. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". Various examples of partial orders appear in
algebra, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include
lattices and
Boolean algebras.
Matroid theory Matroid theory 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. Matroid theory was introduced by
Hassler Whitney and studied as a part of order theory. It is now an independent field of study with a number of connections with other parts of combinatorics.
Extremal combinatorics 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
set systems; 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. The types of questions addressed in this case are about the largest possible graph which satisfies certain properties. For example, the largest
triangle-free graph on
2n vertices is a
complete bipartite graph Kn,n. Often it is too hard even to find the extremal answer
f(
n) exactly and one can only give an
asymptotic estimate.
Ramsey theory is another part of extremal combinatorics. It states that any
sufficiently large configuration will contain some sort of order. It is an advanced generalization of the
pigeonhole principle.
Probabilistic combinatorics in a
square grid graph. In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a
random graph? For instance, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find) by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach (often referred to as
the probabilistic method) proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite
Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the
mixing time. Often associated with
Paul Erdős, who did the pioneering work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. The area recently grew to become an independent field of combinatorics.
Algebraic combinatorics of the
integer partition (5, 4, 1). Algebraic combinatorics is an area of
mathematics that employs methods of
abstract algebra, notably
group theory and
representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in
algebra. Algebraic combinatorics has come to be seen more expansively as an area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. Thus the combinatorial topics may be
enumerative in nature or involve
matroids,
polytopes,
partially ordered sets, or
finite geometries. On the algebraic side, besides group and representation theory,
lattice theory and
commutative algebra are common.
Combinatorics on words . Combinatorics on words deals with
formal languages. It arose independently within several branches of mathematics, including
number theory,
group theory and
probability. It has applications to enumerative combinatorics,
fractal analysis,
theoretical computer science,
automata theory, and
linguistics. While many applications are new, the classical
Chomsky–Schützenberger hierarchy of classes of
formal grammars is perhaps the best-known result in the field.
Geometric combinatorics . Geometric combinatorics is related to
convex and
discrete geometry. It asks, for example, how many faces of each dimension a
convex polytope can have.
Metric properties of polytopes play an important role as well, e.g. the
Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as
permutohedra,
associahedra and
Birkhoff polytopes.
Combinatorial geometry is a historical name for discrete geometry. It includes a number of subareas such as
polyhedral combinatorics (the study of
faces of
convex polyhedra),
convex geometry (the study of
convex sets, in particular combinatorics of their intersections), and
discrete geometry, which in turn has many applications to
computational geometry. The study of
regular polytopes,
Archimedean solids, and
kissing numbers is also a part of geometric combinatorics. Special polytopes are also considered, such as the
permutohedron,
associahedron and
Birkhoff polytope.
Topological combinatorics with two cuts. Combinatorial analogs of concepts and methods in
topology are used to study
graph coloring,
fair division,
partitions,
partially ordered sets,
decision trees,
necklace problems and
discrete Morse theory. It should not be confused with
combinatorial topology which is an older name for
algebraic topology.
Arithmetic combinatorics Arithmetic combinatorics arose out of the interplay between
number theory, combinatorics,
ergodic theory, and
harmonic analysis. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division).
Additive number theory (sometimes also called additive combinatorics) refers to the special case when only the operations of addition and subtraction are involved. One important technique in arithmetic combinatorics is the
ergodic theory of
dynamical systems.
Infinitary combinatorics Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of
set theory, an area of
mathematical logic, but uses tools and ideas from both set theory and extremal combinatorics. Some of the things studied include
continuous graphs and
trees, extensions of
Ramsey's theorem, and
Martin's axiom. Recent developments concern combinatorics of the
continuum and combinatorics on successors of singular cardinals.
Gian-Carlo Rota used the name
continuous combinatorics to describe
geometric probability, since there are many analogies between
counting and
measure. == Related fields ==