![[The Mathematical Atlas]](../images/title.gif)
|
|
[Search] |
![[MathMap Icon]](../images/mini.gif) |
POINTERS: [Texts] 05: Combinatorics |
Combinatorics is, loosely, the science of counting. This is the area of mathematics in which we study families of sets (usually finite) with certain characteristic arrangements of their elements or subsets, and ask what combinations are possible, and how many there are.
This includes numerous quite elementary topics, such as enumerating all possible permutations or combinations of a finite set. Consequently, it is difficult to mention in this page all the topics with which a person new to combinatorics might come into contact. Moreover, because of the approachable nature of the subject, combinatorics is often presented with other fields (elementary probability, elementary number theory, and so on) to the exclusion of the more significant aspects of the subject.
These include more sophisticated methods of counting sets. For example, the cardinalities of sequences of sets are often arranged into power series to form the generating functions, which can then be analyzed using techniques of analysis. (Since many counting procedures involve the binomial coefficients, it is not surprising to see the hypergeometric functions appear frequently in this regard.) In some cases the enumeration is asymptotic (for example the estimates for the number of partitions of an integer). In many cases the counting can be done in a purely synthetic manner using the "umbral calculus". Combinatorial arguments determining coefficients can be used to deduce identities among functions, particularly between infinite sums or products, such as some of the famous Ramanujan identities.
A non-enumerative branch of combinatorics is the study of designs, that is, sets and their subsets arranged into some particularly symmetric or asymmetric pattern. Perhaps most familiar are the Latin squares (arrangements of elements into a rectangular array with no repeats in any row or column). Also famous is the Fano plane (seven points falling into seven "lines", each with three points), which suggests the connection with finite geometries. (Suitably axiomatized, these tend to look like geometries over finite fields, although finite planes are much more flexible.) Matroids may be viewed as generalized geometries; they are included here as well. Of course graphs themselves are designs, although it is only the most regular graphs which are included in these discussions.
A graph is a set V of vertices and a set E of edges -- pairs of elements of V. This simple definition makes Graph Theory the appropriate language for discussing (binary) relations on sets, which is clearly a broad topic; a more detailed description is available on the index page for Graph Theory. Among the topics of interest are topological properties such as connectivity and planarity (can the graph be drawn in the plane?); counting problems (how many graphs of a certain type?); coloring problems (recognizing bipartite graphs, the Four-Color Theorem); paths, cycles, and distances in graphs (can one cross the Köningsberg bridges exactly once each?). There is a significant number of graph-theoretic topics which are the object of complexity studies in computation (e.g. the Traveling Salesman problem, sorting algorithms, the graph-isomorphism problem). The theory also extends to directed, labeled, or multiply-connected graphs.
Extremal set theory looks at questions involving the interaction of sets of subsets of a given set. For example, there is the open conjecture of Frankl: Given a collection of sets closed under the taking of unions, then some element of their union is in at least half of them. Classic results of this type are known collectively as Ramsey theory. (The Ramsey number R_k(n) is the smallest integer N such that whenever the complete graph on N vertices is colored with k colors, there is a monochromatic subgraph with n elements. Since R_2(3)=6, for example, at any gathering of at least 6 people there is either a subset of 3 people who all know one another, or a subset of 3 people none of whom know each other). This area includes matching theorems (e.g. the "marriage problem") and other transversal topics.
Algebraic tools are used in a number of ways in combinatorics. For example, incidence matrices can be associated to graphs, symmetry groups can be associated to block designs, and so on. Particularly common in the study of strongly regular graphs are association schemes. A particular algebraic topic of interest to combinatorialists is the study of Young tableaux, closely connected to the symmetric groups (enumerating, for example, their representations). Codes (in the sense of coding theory) may be considered part of combinatorics, particularly the construction of nonlinear codes.
Note that some combinatorial questions involve well-known sets of numbers (e.g. binomial questions) which are potentially of interest in 11: Number Theory. For example, most questions about partitions are part of 11P: additive number theory. (The partition numbers have also for some reason been a focus of factorization attempts.) Likewise combinatorial questions are often answered with computations in 11T: Finite Fields.
There is considerable overlap between combinatorics and 20: Group Theory. Graphs (and other combinatorial structures) have automorphism groups, some of which are exotic (e.g. the Mathieu groups). The subgroup structures (e.g. coset spaces) of groups can be used to construct some interesting designs; in particular, this is true of the highly transitive groups. Lie groups (and algebras) and their finite analogues are studied through their combinatorial structure (roots systems, buildings, etc.); indeed, a current theme in finite group theory is to generalize this association of finite geometries to other finite groups.
Some combinatorial problems lead nicely to recursions or generating functions, which are treated with, say, series techniques.
A number of classical combinatorial questions are essentially geometric, hence there is interaction with 51: Geometry. Indeed, combinatorial geometry, essentially the theory of polyhedra (52), provided historical precedent for aspects of 57: Algebraic Topology (Betti numbers and so on).
Elementary questions in 60: Probability are essentially combinatorics.
The theory of designs is also a topic in experimental designs, in 62: Statistics.
The complexity of combinatorial optimization problems is treated in 68: Computer Science; in particular, the complexity of combinatorial geometric problems (e.g. choosing furthest pairs of points) is treated with 68U05: Computational Geometry.
Combinatorial games such as Nim are (somewhat incongruously) included in 90D: Game theory (90DXX).
Many important optimization problems involve choices in a large by finite set; this is combinatorial optimization, and is also treated in 90: Operations Research
The general principles of coding theory are part of 94: Information theory
![[Schematic of subareas and related areas]](../images/05b.gif)
Other areas with appreciable overlap:
Combinatorics (Section 05) is one of the larger sections of the Math Reviews database, but this is largely because of the size of Graph Theory (05C), one of the largest of the three-digit areas. Most references to Graph Theory have been moved to a separate index page. (This mirrors a split many years ago in the Journal of Combinatorial Theory -- split into Series A (Combinatorics) and Series B (Graph Theory) !)
Browse all (old) classifications for this area at the AMS.
A comprehensive overview is the huge two-volume "Handbook of Combinatorics", edited by R. L. Graham, M. Grötschel and L. Lovász, Elsevier Science B.V., Amsterdam; MIT Press, Cambridge, MA, 1995. ISBN 0-444-88002-X
For a thorough introduction to the topics of mathematical interest, see e.g.
More appropriate for undergraduates are books such as
The subject is also frequently taught to quite new students, hence there are a number of textbooks covering combinatorics together with matrices, elementary logic, or topics of "discrete mathematics". Textbooks are available in many languages at this level.
Gian-Carlo Rota presented an interesting "Report on the present state of combinatorics"; see Discrete Math. 153 (1996) 289--303. (He is a leader of the field, with a unique perspective.)
In interesting companion is "Classic papers in combinatorics", edited by Ira Gessel and Gian-Carlo Rota, Birkhäuser Boston, Inc., Boston, Mass., 1987. 491 pp. ISBN 0-8176-3364-2 (about 40 papers through 1973)
Klee, Victor: "Combinatorial optimization: what is the state of the art?", Math. Oper. Res. 5 (1980), no. 1, 1--26. MR81b:90146. A longer version appears in "Information linkage between applied mathematics and industry" (Proc. First Annual Workshop, Naval Postgraduate School, Monterey, Cal., 1978), pp. 71--136, Academic Press, New York-London, 1979. MR80i:90067
There is a combinatorics mailing list at comb-l@cmuvm.csv.cmich.edu; Here is mailing list information
Here is a database of some combinatorial objects.
There is a newsgroup alt.sci.math.combinatorics.