Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas ofpure mathematics, notably inalgebra,probability theory,topology, andgeometry,[1] as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving anad hoc solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right.[2] One of the oldest and most accessible parts of combinatorics isgraph theory, which by itself has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in theanalysis of algorithms.
The full scope of combinatorics is not universally agreed upon.[3] According toH. J. Ryser, a definition of the subject is difficult because it crosses so many mathematical subdivisions.[4] Insofar as an area can be described by the types of problems it addresses, combinatorics is involved with:
theenumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
theexistence of such structures that satisfy certain given criteria,
theconstruction of these structures, perhaps in many ways, and
optimization: finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some otheroptimality criterion.
According toLeon Mirsky, "combinatorics is a range of linked studies which have something in common and yet diverge widely in their objectives, their methods, and the degree of coherence they have attained."[5] One way to define combinatorics is, perhaps, to describe its subdivisions with their problems and techniques. This is the approach that is used below. However, there are also purely historical reasons for including or not including some topics under the combinatorics umbrella.[6] Although primarily concerned with finite systems, some combinatorial questions and techniques can be extended to an infinite (specifically,countable) butdiscrete setting.
Basic combinatorial concepts and enumerative results appeared throughout theancient world. The earliest recorded use of combinatorial techniques comes from problem 79 of theRhind papyrus, which dates to the 16th century BC. The problem concerns a certaingeometric series, and has similarities to Fibonacci's problem of counting the number ofcompositions of 1s and 2s thatsum to a given total.[7]IndianphysicianSushruta asserts inSushruta Samhita that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 26 − 1 possibilities.GreekhistorianPlutarch discusses an argument betweenChrysippus (3rd century BCE) andHipparchus (2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related toSchröder–Hipparchus numbers.[8][9][10] Earlier, in theOstomachion,Archimedes (3rd century BCE) may have considered the number of configurations of atiling puzzle,[11] while combinatorial interests possibly were present in lost works byApollonius.[12][13]
In the second half of the 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject.[20] In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, fromfunctional analysis tonumber theory, etc. These connections shed the boundaries between combinatorics and parts of mathematics and theoretical computer science, but at the same time led to a partial fragmentation of the field.
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 broadmathematical 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. Thetwelvefold way provides a unified framework for countingpermutations,combinations andpartitions.
Graphs are fundamental objects in combinatorics. Considerations of graph theory range from enumeration (e.g., the number of graphs onn vertices withk edges) to existing structures (e.g., Hamiltonian cycles) to algebraic representations (e.g., given a graphG and two numbersx andy, does theTutte polynomialTG(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.[21] While combinatorial methods apply to many graph theory problems, the two disciplines are generally used to seek solutions to different types of problems.
Finite geometry is the study ofgeometric 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 fordesign theory. It should not be confused with discrete geometry (combinatorial geometry).
Order theory is the study ofpartially 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 inalgebra, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders includelattices andBoolean algebras.
Matroid theory abstracts part ofgeometry. It studies the properties of sets (usually, finite sets) of vectors in avector space that do not depend on the particular coefficients in alinear dependence relation. Not only the structure but also enumerative properties belong to matroid theory. Matroid theory was introduced byHassler 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 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 concernsclasses ofset systems; this is called extremal set theory. For instance, in ann-element set, what is the largest number ofk-elementsubsets that can pairwise intersect one another? What is the largest number of subsets of which none contains any other? The latter question is answered bySperner'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 largesttriangle-free graph on2n vertices is acomplete bipartite graphKn,n. Often it is too hard even to find the extremal answerf(n) exactly and one can only give anasymptotic estimate.
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 arandom 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 astheprobabilistic method) proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finiteMarkov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate themixing time.[clarification needed]
Often associated withPaul 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 is an area ofmathematics that employs methods ofabstract algebra, notablygroup theory andrepresentation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems inalgebra. 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 beenumerative in nature or involvematroids,polytopes,partially ordered sets, orfinite geometries. On the algebraic side, besides group and representation theory,lattice theory andcommutative algebra are common.
Arithmetic combinatorics arose out of the interplay betweennumber theory, combinatorics,ergodic theory, andharmonic 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 theergodic theory ofdynamical systems.
Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part ofset theory, an area ofmathematical logic, but uses tools and ideas from both set theory and extremal combinatorics. Some of the things studied includecontinuous graphs andtrees, extensions ofRamsey's theorem, andMartin's axiom. Recent developments concern combinatorics of thecontinuum[23] and combinatorics on successors of singular cardinals.[24]
Coding theory started as a part of design theory with early combinatorial constructions oferror-correcting codes. The main idea of the subject is to design efficient and reliable methods of data transmission. It is now a large field of study, part ofinformation theory.
Discrete geometry (also called combinatorial geometry) also began as a part of combinatorics, with early results onconvex polytopes andkissing numbers. With the emergence of applications of discrete geometry tocomputational 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.
^Rota, Gian Carlo (1969).Discrete Thoughts. Birkhaüser. p. 50.doi:10.1007/978-0-8176-4775-9.ISBN978-0-8176-4775-9.... combinatorial theory has been the mother of several of the more active branches of today's mathematics, which have become independent ... . The typical ... case of this is algebraic topology (formerly known as combinatorial topology)
^Biggs, Norman; Lloyd, Keith; Wilson, Robin (1995). "44". In Ronald Grahm, Martin Grötschel, László Lovász (ed.).Handbook of Combinatorics(Google book). MIT Press. pp. 2163–2188.ISBN0262571722. Retrieved2008-03-08.{{cite book}}: CS1 maint: multiple names: editors list (link)
^Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough",American Mathematical Monthly104 (1997), no. 4, 344–350.
^Habsieger, Laurent; Kazarian, Maxim; Lando, Sergei (1998). "On the Second Number of Plutarch".The American Mathematical Monthly.105 (5): 446.doi:10.1080/00029890.1998.12004906.
^White, Arthur T. (1996). "Fabian Stedman: The First Group Theorist?".The American Mathematical Monthly.103 (9):771–778.doi:10.1080/00029890.1996.12004816.
Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. (1996);Handbook of Combinatorics, Volumes 1 and 2. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press.ISBN0-262-07169-X
Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997);Design Theory, CRC-Press.ISBN0-8493-3986-3.
