[Search] |

ABOUT:
[Introduction]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

Other areas with appreciable overlap:

- 92: Natural sciences
- 06: Ordered structures
- 15: Linear algebra
- 03: Logic and foundations
- Packing and covering is related to the sphere FAQ.

- 05A: Enumerative combinatorics [Classical combinatorial problems]
- 05B: Designs and configurations, For applications of design theory, see 94C30
- 05C: Graph theory
- 05D: Extremal combinatorics
- 05E: Algebraic combinatorics

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.

- "Combinatorial theory", by Marshall Hall, Jr. John Wiley & Sons, Inc., New York, 1986. ISBN 0-471-09138-3.
- "A course in combinatorics", J.H. van Lint and R.M. Wilson, Cambridge University Press, Cambridge, 1992. ISBN 0-521-41057-6; 0-521-42260-4: comprehensive.
- "Combinatorial methods in discrete mathematics", by Vladimir N. Sachkov, Encyclopedia of Mathematics and its Applications, 55. Cambridge University Press, Cambridge, 1996. ISBN 0-521-45513-8
- Extremal problems are treated quite nicely in "Ramsey theory", by Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H.; John Wiley & Sons, Inc., New York, 1990. 196 pp. ISBN 0-471-50046-1, MR90m:05003

More appropriate for undergraduates are books such as

- "Introductory combinatorics", by Richard A. Brualdi, North-Holland Publishing Co., New York, 1992. ISBN 0-444-01616-3
- "An introduction to combinatorics", by Alan Slomson, Chapman and Hall, Ltd., London, 1991. ISBN 0-412-35370-9
- "Applied combinatorics", by Alan Tucker, John Wiley & Sons, Inc., New York, (3rd edition) 1995. 462 pp. ISBN 0-471-59504-7 covers quite a bit of territory but focuses on examples rather than theoretical development

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

- The Stony Brook Algorithm Repository
- ACE -- an Algebraic Combinatorics module for Maple.
- SF -- a Symmetric Functions module for Maple.
- Packages for Mathematica, versions 2.2 and 3.0. especially Combinatorica: A Mathematica Package for Combinatorics and Graph Theory
- The Magma system is well suited to combinatorial as well as algebraic structures.
- LEDA handles combinatoric and graph-theoretic problems as well as discrete geometry.
- Sometimes the easiest way to get information on a counting problem is to compute a few small values of a function, then look for a match at the sequence server; if you find a hit, you can sometimes get citations to the literature.
- Snippets of C code for permutations, etc.
- Integer-valued functions software.

Here is a database of some combinatorial objects.

There is a newsgroup alt.sci.math.combinatorics.

- From the homepage of the Electronic Journal of Combinatorics one may jump to a set of dynamic surveys on several topics in combinatorics.
- From the homepage of the Springer Annals of Combinatorics one may jump to a "hyperbook" linking to surveys on several topics in combinatorics.
- Small Ramsey numbers.
- A compendium of NP optimization problems
- Overview of Modern Heuristic Methods of combinatorial optimization
- Preprint server at Los Alamos.
- Matroid Theory index.
- Here are the AMS and Goettingen resource pages for area 05.
- UTK archives page

- How to list all subsets of a given cardinality of a given set.
- Elementary problem: how to enumerate subsets with distinct labels?
- Enumerating all permutations of a finite set
- Sample counting problem: how many ways of drawing balls from urns?
- How many ways to select at most one item in each subset... (Generic counting problem)
- Pointer: derivation of formula for number of derangements
- Stirling numbers of the second kind: counting ways to arrange N objects into K subsets.
- Probability that adjacent cards have different values (standard deck)
- Odds of a run of given length existing in a sequence
- Minimum number of telephone calls to exchange information
- A knight's tour (but cannot be a magic square)
- Langford problem (sequence 2 sets of first n numbers with each pair suitably far apart)
- Recursive formulas for partition functions
- How many ways to slice the cake (in n dimensions)?
- Sperner's Theorem: the maximum number of incomparable subsets of a k-element set is C(k,k/2)
- Sperner's theorem on maximal collections of incomparable subsets
- Subsets of a committee meet several times... incidence problems and combinatorial geometries
- Number of ways N ordered whole numbers, each no greater than N, add up to N^2-N. (A classic counting problem)
- Frankl conjecture on finite sets (open)
- What are Steiner systems?
- Steiner systems: what they are, example of construction
- Application of Steiner systems to lottery analysis
- Efficient orthogonal array generation
- Balanced tournament designs
- Block Scheduling Algorithm for tournaments
- Scheduling tournaments for Whist, bridge, golf, tennis
- The "most rapidly increasing function": the Ackermann function
- Ackermann function -- pointers and code
- Prüfer codes to count labeled trees
- Philip Hall's marriage theorem (making a matched set from a collection of sets)
- The Set Partitioning problem: find a collection of subsets which cover the whole set
- A set-covering problem (which arose in weaving!)
- Finding Graeco-Latin squares
- Kirkman's schoolgirl problem (block design)
- How many ways to group p people into n teams?
- Interesting problem still open: Given some sticks of integral length at least n, whose total length is n(n+1)/2, can one cut them into pieces of length 1, 2, ..., n?
- Generating linear extensions of posets.
- The Möbius inversion function on posets
- Additive computability -- if S_1 = {1}, S_2 = {1,2}, and S_m= S_(m-1) \union (S_(m-1) + S_(m-1)) , what's the first set S_m containing a given n?
- Pointer to software for combinatorial optimization (shortest path, etc.)
- Comparison of assignment problem and traveling salesman problem.
- An assignment problem (optimally split people into groups)
- A general optimization problem between the knapsack problem and sphere-packing problems.
- The Knapsack problem: finding subsets of a set of integers which add to a given total.
- The subset-sum problem: solving exactly (hard) or approximately (easy)
- The subset-sum problem (minimize the sum of a set of reals)
- Ramsey Theory: complete disorder is impossible
- Known values of Ramsey numbers
- Proving weak estimates for Ramsey numbers R(k,k)
- Ramsey numbers for 3-colored sets
- Table of some known Ramsey numbers
- Van Der Waerden's theorem on coloring coloring arithmetic progressions.
- Number of partial orders on a finite set
- Famous conjectures: existence of Hadamard matrices, projective planes, Jacobian conjecture

Last modified 2000/01/14 by Dave Rusin. Mail: