nLab combinatorics

Contents

Context

Combinatorics

combinatorics

enumerative combinatorics

graph theory

rewriting

Polytopes

edit this sidebar

category: combinatorics

Contents

Idea

Combinatorics is a subfield of discrete mathematics 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”.

References

category: combinatorics

Last revised on June 1, 2021 at 11:14:01. See the history of this page for a list of all contributions to it.