nLab combinatorics

Idea

Combinatorics is a field whose main subject (defining its central subfield of enumerative combinatorics) is the study of cardinality of finite sets of data, which are described by elementary rules, and reducing the question of cardinality of more complicated data to simpler such “combinatorial” problems. The basic method of combinatorics is to find bijections between two sets of data defined in manifestly different way, and in particular to find the bijections between the sets of more complicated and less explicit origin, with the sets whose definition and structure is more explicit, and considered more manageable (by already known “combinatorial” means). For example, a typical bijection the isomorphisms classes of representations of some object (e.g. of a group) and “combinatorial” data like Young tableaux, graphs of some kind and so on (this comprises combinatorial representation theory).

More widely, combinatorics is also studying various deterministic algorithms on finite sets with structure, involving counting, coloring and simple-minded elementary steps/decisions. When studying some other structure, which is not necessarily a finite structure, one can use “combinatorial arguments’ at some step, or develop a construction which is partly combinatorial. Some subclasses of examples of structures in mathematics are fully combinatorial in their nature. For example, there are so called combinatorial games in game theory.

Some of the questions in set and model theory concerning the fine questions on cardinality of infinite sets (and their independence from various axioms in set theory) are often called the “infinitary combinatorics”.

Related entries

• graph, quiver

• matroid, oriented matroid

• permutation

• symmetric function, noncommutative symmetric function

• Schur functor, Schur function, plethysm

• (combinatorial) species

• combinatorial functor

• Catalan number, Motzkin number, Moebius function

• game theory

• combinatorial representation theory

• enumerative combinatorics

References

• Richard Stanley, Enumerative combinatorics – Volume 1, 2011 (pdf)

• Richard Stanley, Enumerative combinatorics 2, Cambridge University Press (1999, 2010) (doi:10.1017/CBO9780511609589, webpage)

• Bruce Sagan, Combinatorics: The Art of Counting, Graduate studies in Mathematics 210, AMS (ISBN:978-1-4704-6032-7 pdf)

• Martin Aigner, A Course in Enumeration, Springer 2007 (doi:10.1007/978-3-540-39035-0)

On combinatorics in algebraic topology:

• Dmitry N. Kozlov, Trends in topological combinatorics [arXiv:math/0507390]

• Dmitry Kozlov, Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics 21, Springer (2008) [doi:10.1007/978-3-540-71962-5]

An application of Hodge theory:

• June Huh, Combinatorics and Hodge theory, Proc. Int. Cong. Math. 1 (2022)

  [doi:10.4171/ICM2022/205, pdf, pdf]

A categorification of many counting procedures may be viewed via so called objective linear algebra:

• Imma Gálvez-Carrillo, Joachim Kock, Andrew Tonks, Decomposition spaces, incidence algebras and Möbius inversion, arXiv:1404.3202

On using integrable systems for solving combinatorics problems:

• Paul Zinn-Justin, Integrability and combinatorics, in Encyclopedia of Mathematical Physics 2nd ed, Elsevier (2024) [arXiv:2404.13221]

category: combinatorics