Combinatorics

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (July 2022) (Learn how and when to remove this template message)

Part of a series on
Mathematics
History Outline Index
Areas Number theory Geometry Algebra Calculus and Analysis Discrete mathematics Logic and Set theory Probability Statistics and Decision theory Relationship with sciences Physics Chemistry Geosciences Computation Biology Linguistics Economics Philosophy Education
Mathematics Portal
v t e

Combinatorics is an area of

Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry,^[1] as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ad 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 is graph theory, which by itself has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms.

A mathematician who studies combinatorics is called a combinatorialist.

Definition

The full scope of combinatorics is not universally agreed upon.

Leon Mirsky has said: "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) but discrete setting.

History

Basic combinatorial concepts and enumerative results appeared throughout the ancient world. Indian physician Sushruta asserts in Sushruta 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 2⁶ − 1 possibilities. Greek historian Plutarch discusses an argument between Chrysippus (3rd century BCE) and Hipparchus (2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to Schröder–Hipparchus numbers.^[7][8][9] Earlier, in the Ostomachion, Archimedes (3rd century BCE) may have considered the number of configurations of a tiling puzzle,^[10] while combinatorial interests possibly were present in lost works by Apollonius.^[11][12]

In the

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.[19] In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from functional analysis to number 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.

Approaches and subfields of combinatorics

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

Partition theory studies various enumeration and asymptotic problems related to

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 T_G(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.^[20] 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

Finite geometry is the study of

Order theory

Order theory is the study of

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

Main article:

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 K_n,n. Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate.

sufficiently large configuration will contain some sort of order. It is an advanced generalization of the pigeonhole principle

.

Probabilistic combinatorics

Main article: Probabilistic method

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

Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time.^{[clarification needed}

]

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

Young diagram of the integer partition

(5, 4, 1).

Main article: Algebraic combinatorics

Algebraic combinatorics is an area of

lattice theory and commutative algebra

are common.

Combinatorics on words

Main article: Combinatorics on words

Combinatorics on words deals with

Chomsky–Schützenberger hierarchy of classes of formal grammars

is perhaps the best-known result in the field.

Geometric combinatorics

Main article: Geometric combinatorics

Geometric combinatorics is related to

Combinatorial geometry

is a historical name for discrete geometry.

It includes a number of subareas such as

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

Main article: 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. It should not be confused with combinatorial topology which is an older name for algebraic topology.

Arithmetic combinatorics

Main article: 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

Main article: Infinitary combinatorics

Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of

continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum^[22] and combinatorics on successors of singular cardinals.^[23]

Gian-Carlo Rota used the name continuous combinatorics^[24] to describe geometric probability, 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

error-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 of information theory

.

Discrete and computational geometry

Discrete geometry (also called combinatorial geometry) also began as 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 dynamical systems

Combinatorial aspects of dynamical systems is another emerging field. Here dynamical systems can be defined on combinatorial objects. See for example graph dynamical system.

Combinatorics and physics

There are increasing interactions between

statistical physics. Examples include an exact solution of the Ising model, and a connection between the Potts model on one hand, and the chromatic and Tutte polynomials

on the other hand.

See also

• Combinatorial biology
• Combinatorial chemistry
• Combinatorial data analysis
• Combinatorial game theory
• Combinatorial group theory
• Discrete mathematics
• List of combinatorics topics
• Phylogenetics
• Polynomial method in combinatorics

Notes

1. ^ Björner and Stanley, p. 2
2. ISBN 978-0821842621. Archived
   from the original on 2021-04-16. Retrieved 2021-03-23. In my opinion, combinatorics is now growing out of this early stage.
3. ^ Pak, Igor. "What is Combinatorics?". Archived from the original on 17 October 2017. Retrieved 1 November 2017.
4. ^ Ryser 1963, p. 2
5. doi:10.1090/S0273-0979-1979-14606-8, archived
   (PDF) from the original on 2021-02-26, retrieved 2021-02-04
6. ISBN 978-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)
7. S2CID 122758966. Archived
   from the original on 2022-01-23. Retrieved 2021-03-12.
8. ^ Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), no. 4, 344–350.
9. doi:10.1080/00029890.1998.12004906
   .
10. ^ Netz, R.; Acerbi, F.; Wilson, N. "Towards a reconstruction of Archimedes' Stomachion". Sciamvs. 5: 67–99. Archived from the original on 2021-04-16. Retrieved 2021-03-12.
11. S2CID 121613986. Archived
    from the original on 2021-04-18. Retrieved 2021-03-26.
12. ^ Huxley, G. (1967). "Okytokion". Greek, Roman, and Byzantine Studies. 8 (3): 203. Archived from the original on 2021-04-16. Retrieved 2021-03-26.
13. ^ O'Connor, John J.; Robertson, Edmund F., "Combinatorics", MacTutor History of Mathematics Archive, University of St Andrews
14. ISBN 978-1-4020-0260-1. Archived
    from the original on 2021-04-16. Retrieved 2015-11-15.
15. doi:10.1016/0315-0860(79)90074-0
    .
16. ISBN 978-1-4832-1863-2, archived
    from the original on 2021-04-16, retrieved 2015-01-25. (Translation from 1967 Russian ed.)
17. doi:10.1080/00029890.1987.12000711
    .
18. doi:10.1080/00029890.1996.12004816
    .
19. ^ See Journals in Combinatorics and Graph Theory Archived 2021-02-17 at the Wayback Machine
20. ^ Sanders, Daniel P.; 2-Digit MSC Comparison Archived 2008-12-31 at the Wayback Machine
21. ^ Stinson 2003, pg.1
22. ^ Andreas Blass, Combinatorial Cardinal Characteristics of the Continuum, Chapter 6 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010
23. ISBN 978-1-4020-4843-2
    , retrieved 2022-08-27
24. ^ "Continuous and profinite combinatorics" (PDF). Archived (PDF) from the original on 2009-02-26. Retrieved 2009-01-03.

References

• Björner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany
• Bóna, Miklós; (2011); A Walk Through Combinatorics (3rd ed.).
  ISBN 978-981-4335-23-2, 978-981-4460-00-2
• 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.
  ISBN 0-262-07169-X
• Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); Design Theory, CRC-Press.
  ISBN 0-8493-3986-3
  .
• ISBN 978-0-486-42536-8
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs(#14), The Mathematical Association of America
• ISBN 0-521-55309-1, 0-521-56069-1
• Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis, New York: Springer,
  ISBN 0-387-95487-2
• van Lint, Jacobus H.; and Wilson, Richard M.; (2001); A Course in Combinatorics, 2nd ed., Cambridge University Press.
  ISBN 0-521-80340-3

External links

• "Combinatorial analysis", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
• Combinatorics, a MathWorld article with many references.
• Combinatorics, from a MathPages.com portal.
• The Hyperbook of Combinatorics, a collection of math articles links.
• The Two Cultures of Mathematics by W.T. Gowers, article on problem solving vs theory building.
• "Glossary of Terms in Combinatorics" Archived 2017-08-17 at the Wayback Machine
• List of Combinatorics Software and Databases