Combinatorics is an area of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
primarily concerned with
counting, both as a means and an end in obtaining results, and certain properties of
finite structures. It is closely related to many other areas of mathematics and has many applications ranging from
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from prem ...
to
statistical physics and from
evolutionary biology
Evolutionary biology is the subfield of biology that studies the evolutionary processes (natural selection, common descent, speciation) that produced the diversity of life on Earth. It is also defined as the study of the history of life ...
to
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
.
Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of
pure mathematics, notably in
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
,
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
,
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
, and
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, 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. One of the oldest and most accessible parts of combinatorics is
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, 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
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
who studies combinatorics is called a '.
Definition
The full scope of combinatorics is not universally agreed upon. According to
H.J. Ryser, a definition of the subject is difficult because it crosses so many mathematical subdivisions. Insofar as an area can be described by the types of problems it addresses, combinatorics is involved with:
* the ''enumeration'' (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
* the ''existence'' of such structures that satisfy certain given criteria,
* the ''construction'' 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 other ''optimality criterion''.
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." 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. 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. In the 6th century BCE,
ancient Indian
The following outline is provided as an overview of and topical guide to ancient India:
Ancient India is the Indian subcontinent from prehistoric times to the start of Medieval India, which is typically dated (when the term is still used) to t ...
physician Sushruta
Sushruta, or ''Suśruta'' (Sanskrit: सुश्रुत, IAST: , ) was an ancient Indian physician. The '' Sushruta Samhita'' (''Sushruta's Compendium''), a treatise ascribed to him, is one of the most important surviving ancient treatises o ...
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
6 − 1 possibilities.
Greek historian
A historian is a person who studies and writes about the past and is regarded as an authority on it. Historians are concerned with the continuous, methodical narrative and research of past events as relating to the human race; as well as the st ...
Plutarch discusses an argument between
Chrysippus (3rd century BCE) and
Hipparchus
Hipparchus (; el, Ἵππαρχος, ''Hipparkhos''; BC) was a Greek astronomer, geographer, and mathematician. He is considered the founder of trigonometry, but is most famous for his incidental discovery of the precession of the e ...
(2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to
Schröder–Hipparchus numbers. Earlier, in the ''
Ostomachion'',
Archimedes (3rd century BCE) may have considered the number of configurations of a
tiling puzzle, while combinatorial interests possibly were present in lost works by
Apollonius.
In the
Middle Ages
In the history of Europe, the Middle Ages or medieval period lasted approximately from the late 5th to the late 15th centuries, similar to the post-classical period of global history. It began with the fall of the Western Roman Empire ...
, combinatorics continued to be studied, largely outside of the
European civilization. The
India
India, officially the Republic of India (Hindi: ), is a country in South Asia. It is the List of countries and dependencies by area, seventh-largest country by area, the List of countries and dependencies by population, second-most populous ...
n mathematician
Mahāvīra () provided formulae for the number of
permutations and
combinations, and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE. The
philosopher and
astronomer
An astronomer is a scientist in the field of astronomy who focuses their studies on a specific question or field outside the scope of Earth. They observe astronomical objects such as stars, planets, moons, comets and galaxies – in either ...
Rabbi
Abraham ibn Ezra () established the symmetry of
binomial coefficients, while a closed formula was obtained later by the
talmudist and
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Levi ben Gerson (better known as Gersonides), in 1321.
The arithmetical triangle—a graphical diagram showing relationships among the binomial coefficients—was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as
Pascal's triangle. Later, in
Medieval England,
campanology provided examples of what is now known as
Hamiltonian cycles in certain
Cayley graphs on permutations.
During the
Renaissance
The Renaissance ( , ) , from , with the same meanings. is a period in European history marking the transition from the Middle Ages to modernity and covering the 15th and 16th centuries, characterized by an effort to revive and surpass ide ...
, together with the rest of mathematics and the
science
Science is a systematic endeavor that builds and organizes knowledge in the form of testable explanations and predictions about the universe.
Science may be as old as the human species, and some of the earliest archeological evidence ...
s, combinatorics enjoyed a rebirth. Works of
Pascal
Pascal, Pascal's or PASCAL may refer to:
People and fictional characters
* Pascal (given name), including a list of people with the name
* Pascal (surname), including a list of people and fictional characters with the name
** Blaise Pascal, Frenc ...
,
Newton,
Jacob Bernoulli and
Euler became foundational in the emerging field. In modern times, the works of
J.J. Sylvester (late 19th century) and
Percy MacMahon (early 20th century) helped lay the foundation for
enumerative
An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration ...
and
algebraic combinatorics.
Graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
also enjoyed an increase of interest at the same time, especially in connection with the
four color problem.
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. In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from
functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defi ...
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
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
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
,
combinations and
partitions
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of ...
.
Analytic combinatorics
Analytic combinatorics concerns the enumeration of combinatorial structures using tools from
complex analysis and
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and
generating functions to describe the results, analytic combinatorics aims at obtaining
asymptotic formulae.
Partition theory
Partition theory studies various enumeration and asymptotic problems related to
integer partition
In number theory and combinatorics, a partition of a positive integer , also called an integer partition, is a way of writing as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same part ...
s, and is closely related to
q-series
In mathematical area of combinatorics, the ''q''-Pochhammer symbol, also called the ''q''-shifted factorial, is the product
(a;q)_n = \prod_^ (1-aq^k)=(1-a)(1-aq)(1-aq^2)\cdots(1-aq^),
with (a;q)_0 = 1.
It is a ''q''-analog of the Pochhammer s ...
,
special functions and
orthogonal polynomials. Originally a part of
number theory and
analysis
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (3 ...
, it is now considered a part of combinatorics or an independent field. It incorporates the
bijective approach and various tools in analysis and
analytic number theory and has connections with
statistical mechanics. Partitions can be graphically visualized with
Young diagrams or
Ferrers diagrams. They occur in a number of branches of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
physics
Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which ...
, including the study of
symmetric polynomials and of the
symmetric group and in
group representation theory in general.
Graph theory
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. 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
combinatorial designs, which are collections of subsets with certain
intersection properties.
Block designs are combinatorial designs of a special type. This area is one of the oldest parts of combinatorics, such as in
Kirkman's schoolgirl problem proposed in 1850. The solution of the problem is a special case of a
Steiner system, which systems play an important role in the
classification of finite simple groups. The area has further connections to
coding theory and geometric combinatorics.
Combinatorial design theory can be applied to the area of
design of experiments
The design of experiments (DOE, DOX, or experimental design) is the design of any task that aims to describe and explain the variation of information under conditions that are hypothesized to reflect the variation. The term is generally associ ...
. Some of the basic theory of combinatorial designs originated in the statistician
Ronald Fisher's work on the design of biological experiments. Modern applications are also found in a wide gamut of areas including
finite geometry,
tournament scheduling,
lotteries,
mathematical chemistry,
mathematical biology,
algorithm design and analysis,
networking
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematic ...
,
group testing and
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
.
Finite geometry
Finite geometry is the study of
geometric 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 for
design theory
Design theory is a subfield of design research concerned with various theoretical approaches towards understanding and delineating design principles, design knowledge, and design practice.
History
Design theory has been approached and interp ...
. It should not be confused with discrete geometry (
combinatorial geometry).
Order theory
Order theory is the study of
partially ordered sets
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
, 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 in
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
, 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
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
. 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
Extremal combinatorics studies how large or how small a collection of finite objects (
number
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual number ...
s,
graphs,
vectors,
sets, etc.) can be, if it has to satisfy certain restrictions. Much of extremal combinatorics concerns
classes of
set system
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fa ...
s; this is called extremal set theory. For instance, in an ''n''-element set, what is the largest number of ''k''-element
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
s 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
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.
As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as beco ...
.
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) by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach (often referred to as ''the''
probabilistic method) 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 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. However, with the growth of applications to
analyze algorithms in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, as well as classical probability,
additive number theory, and
probabilistic number theory, the area recently grew to become an independent field of combinatorics.
Algebraic combinatorics
Algebraic combinatorics is an area of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
that employs methods of
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
, notably
group theory
In abstract algebra, group theory studies the algebraic structures known as groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen ...
and
representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
. 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 be
enumerative
An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration ...
in nature or involve
matroids,
polytopes,
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
s, or
finite geometries. On the algebraic side, besides group and representation theory,
lattice theory and
commutative algebra
Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra. Prom ...
are common.
Combinatorics on words
Combinatorics on words deals with
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sym ...
s. It arose independently within several branches of mathematics, including
number theory,
group theory
In abstract algebra, group theory studies the algebraic structures known as groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen ...
and
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, ...
. It has applications to enumerative combinatorics,
fractal analysis,
theoretical computer science,
automata theory, and
linguistics
Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Ling ...
. 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. It asks, for example, how many faces of each dimension a
convex polytope can have.
Metric properties of polytopes play an important role as well, e.g. the
Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as
permutohedra,
associahedra and
Birkhoff polytopes.
Combinatorial geometry is a historical name for discrete geometry.
It includes a number of subareas such as
polyhedral combinatorics (the study of
faces of
convex polyhedra),
convex geometry
In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of ...
(the study of
convex set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex ...
s, 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
Combinatorial analogs of concepts and methods in
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
are used to study
graph coloring,
fair division,
partitions
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of ...
,
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
s,
decision trees,
necklace problems and
discrete Morse theory. It should not be confused with
combinatorial topology which is an older name for
algebraic topology
Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism, though usually most classify ...
.
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 system
In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water i ...
s.
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
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
, an area of
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
, but uses tools and ideas from both set theory and extremal combinatorics. Some of the things studied include
continuous graphs and
trees, extensions of
Ramsey's theorem, and
Martin's axiom
In the mathematical field of set theory, Martin's axiom, introduced by Donald A. Martin and Robert M. Solovay, is a statement that is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, but it is consis ...
. Recent developments concern combinatorics of the
continuum and combinatorics on successors of singular cardinals.
Gian-Carlo Rota used the name ''continuous combinatorics''
to describe
geometric probability
Problems of the following type, and their solution techniques, were first studied in the 18th century, and the general topic became known as geometric probability.
* (Buffon's needle) What is the chance that a needle dropped randomly onto a floo ...
, 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
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...
,
algorithm theory and
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
.
Coding theory
Coding theory started as a part of design theory with early combinatorial constructions of
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
combinatorics and physics, particularly
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
References
* Björner, Anders; and Stanley, Richard P.; (2010)
''A Combinatorial Miscellany''* Bóna, Miklós; (2011)
''A Walk Through Combinatorics (3rd Edition)''
* 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.
* Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); ''Design Theory'', CRC-Press; 1st. edition (1997). .
*
*
*
Stanley, Richard P. (1997, 1999)
''Enumerative Combinatorics'', Volumes 1 and 2 Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer.
Cambridge University Pr ...
.
*
* van Lint, Jacobus H.; and Wilson, Richard M.; (2001); ''A Course in Combinatorics'', 2nd Edition, Cambridge University Press.
External links
*
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 Mathematicsby W.T. Gowers, article on problem solving vs theory building.
{{Authority control