|
|
|
|
Combinatorics
|
| |
|
| |
Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics. Aspects of combinatorics include "counting" the objects satisfying certain criteria (enumerative combinatorics), deciding when the criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and finding algebraic structures these objects may have (algebraic combinatorics).
Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth century.
Discussion
Ask a question about 'Combinatorics' Start a new discussion about 'Combinatorics' Answer questions from other users |
Encyclopedia
Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics. Aspects of combinatorics include "counting" the objects satisfying certain criteria (enumerative combinatorics), deciding when the criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and finding algebraic structures these objects may have (algebraic combinatorics).
Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth century. One of the oldest and most accessible parts of combinatorics is graph theory, which also has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain estimates on the number of elements of certain sets.
A mathematician who studies combinatorics is often referred to as a combinatorialist or combinatorist.
History of combinatorics
The concepts of combinatorics can be traced back at the latest to the advent of Jainism in India. Before the Jains, Sushruta (in Sushruta Samhita) asserts that 63 combinations can be made out of 6 different tastes, taken one at a
time, two at a time, etc. Pingala gives the method of determining the number of combinations of a given number
of letters, taken one at a time, two at a time, etc. The Jains first treated its subject matter as a self-contained topic in mathematics, under the name Vikalpa. Mahavira (c. 850) provided the general formulae for permutations and combinations. Bhaskaracharya treated combinatorics under the name Anka Pasha in Lilavati. In
addition to the general formulae for nCr and nPr already provided by Mahavira, Bhaskaracharya gives several important theorems and results concerning the subject.
A number of basic results were also obtained in Ancient Greece and China. For example, in the Ostomachion, Archimedes calculates the number of solutions of a certain tiling puzzle.
Some Arabic and Hebrew writers used the concepts of permutations and combinations in studying astronomy. Rabbi ben Ezra (c. 1140), for instance, determined the number of combinations of known planets taken two at a time, three at a time and so on. In more recent times campanology provided examples of Hamiltonian cycles in certain Cayley graphs on permutations. The first modern book on combinatorics was Ars Conjectandi written by Jacob Bernoulli, posthumously published in 1713.
Enumerative combinatorics
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, the analytic combinatorics aims at obtaining the 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, analytic number theory, and has connections with statistical mechanics.
Graph theory
Graphs are basic objects in combinatorics. The questions range from counting (e.g. the number of graphs on n vertices with k edges) to structural (e.g. which graphs contain Hamiltonian cycles) to algebraic questions (e.g. given a graph G and two numbers x and y, does the Tutte polynomial TG(x,y) have a combinatorial interpretation?). It should be noted that while there are very strong connections between graph theory and combinatorics, these two are sometimes thought of as separate subjects.
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 one oldest parts of combinatorics, such as in Kirkman's schoolgirl problem proposed in 1850. The solution of the problem is a special case of 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.
Order theory
Order theory is the study of partially ordered sets, both finite and infinite. 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 the 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 extremal questions on set systems. 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 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), simply by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach 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 Erdos, who did the pioneer work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. However, with the growth of applications to analysis of algorithms in computer science, as well as classical probability, additive and probabilistic number theory, the area recently grew to become an independent field of combinatorics.
Algebraic combinatorics
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. Within the last decade or so, algebraic combinatorics came to be seen more expansively as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. One of the fastest developing subfields within algebraic combinatorics is combinatorial commutative algebra.
Combinatorics on words
Combinatorics on words is an area of combinatorics which studies 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, in particular polyhedral combinatorics. It asks, e.g. how many faces of each dimension can a convex polytope have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on rigidity of convex polytopes. Special polytopes are also considered, such as permutohedron, associahedron and Birkhoff polytope.
Topological combinatorics
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.
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 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.
Gian-Carlo Rota used the name continuous combinatorics to describe probability and measure theory, since there are many analogies between counting and measure.
Related fields
Combinatorial optimization
Combinatorial optimization is the study of optimization on discrete and combinatorial objects. It started as a part of combinatorics and graph theory, but is now viewed as a branch of applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory.
Coding theory
Coding theory started as a part of design theory with early combinatorial constructions of error-correcting codes. It is now a large field of study, part of the information theory.
Discrete and computational geometry
Discrete geometry (also called combinatorial geometry) also began a part of combinatorics, with early results on convex polytopes and kissing numbers. With the emergence of applications of discrete geometry to computational geometry, these two fields partially merged and became a separate field of study. There remain many connections with geometric and topological combinatorics, which themselves can be viewed as outgrowths of the early discrete geometry.
Combinatorics and functional analysis
Combinatorics and functional analysis is the study of combinatorial aspects of functional analysis. An important example is the umbral calculus, which has important connections to enumerative combinatorics. Functional analysis is also involved in infinitary combinatorics. Various combinatorial problems arise in the study of rearrangement in functional analysis.
Combinatorics and dynamical systems
Combinatorial aspects of dynamical systems is another emerging field. Here dynamical systems can be defined on combinatorial objects. For example, graph dynamical system is a sequential dynamical system.
See also
External links
- , a MathWorld article with many references.
- , from a MathPages.com portal.
- , a collection of math articles links.
|
| |
|
|
