Why is it important to study combinatorics?

As requested, here is a list of applications of combinatorics to other topics in pure mathematics.

  • Counting is used extensively in the original proof of Chebyshev's theorem, which you can find in Chapter 5 of (the free online version of) this book. Chebyshev's theorem is the first part of the prime number theorem, a deep result from analytic number theory.

  • In group theory, the pigeonhole principle is used to show that every element of a finite group has an order. One could argue that the proof that every finite integral domain is a field stems from similar logic.

  • A proof of Brouwer's fixed point theorem using the pigeonhole principle and Sperner's lemma is given here.

  • UPDATE: Graphs in Finite Group Theory. I know of several examples where graphs appear in finite group theory: prime graphs, character degree graphs, and commuting graphs. Prime graphs (about which I have written several MSE answers, e.g. $[1]$,$[2]$) concern the set of element orders in a finite group, character degree graphs have to do with the degrees of a group's irreducible characters, and commuting graphs illustrate which elements commute with which other elements. $$$$ Most of the time, the application of graph theory to finite group theory is linguistic - that is, these graphs arise naturally from group theoretic questions that are best formulated using graph theoretic language. In other words, one doesn't commonly see theorems from graph theory being used to solve problems in finite group theory, even when the aforementioned graphs are the subject of research. Sometimes, however, graph theory may also be applied more directly, as can be seen in this paper of mine, for example.


We might wonder: How important is "importance"? :)

But for a more serious general response to the concerns that perhaps underlie your question, it is well worth reading this wonderful piece by Sir Timothy Gowers in which he talks about two cultures or styles of mathematics, problem-solving vs theory-building, exemplified it might seem at first sight by e.g. combinatorialists vs topos theorists (the latter is my example). Gowers goes on to defend the mathematical interest and importance of combinatorics, and seeks explicitly to “counter the suggestion that the subject of combinatorics has very little structure and consists of nothing but a large number of problems”.


The entire modern world relies on combinatorial algorithms. If you want to make a program faster, you need combinatorics. If you want to understand modern programming, you need combinatorics. Without combinatorics, some programs that now take a split second would require weeks.

Cellphone communications -- Error correcting codes, wavelet and fourier optimizations.
Game programming -- polygon optimization
This website -- comment hierarchies

Anyplace you have a hundred or more pieces of data -- which is pretty much every site, store, program, place, or project -- there is likely some combinatorial improvement being used. Especially in programs. If it's fast, there are combinatorics helping out.


Another important application of combinatorics is in representation theory, symmetric functions, and the study of varieties with lots of symmetries (Grassmannians, flag varieties, toric varieties, symmetric varieties, spherical varieties).

In general, objects with enough symmetries can often be described by discrete (often finite) data. Combinatorics comes into play in order to parameterize the data and, more generally, because relationships between objects are often described in terms of combinatorics of the data.

As a simple example, suppose you want to study $k$-dimensional subspaces of an $n$-dimensional vector space $V$. One way to understand such a subspace $W$ is to consider a "flag" of $V$, which is a sequence of subspaces $$0 = V_0 \subset V_1 \subset \dots \subset V_i \subset \dots \subset V_n = V,$$ with $\dim(V_i) = i$. You can divide the different subspaces $W$ based on the weakly increasing sequence of numbers $$0 = \dim(W \cap V_0) \leq \dim(W \cap V_1) \leq \dots \leq \dim(W \cap V_i) \leq \dots \leq \dim(W \cap V_n) = k,$$ with the restriction that at each stage the dimension can go only up 1 or stay the same. An equivalent way to describe the position of $W$ relative to the flag is to give a sequence of length $n$ consisting of $k$ 1's and $n-k$ 0's, with a $1$ occurring in the $i$-th position exactly when $\dim(W \cap V_i) > \dim(W \cap V_{i-1})$.

A simple observation is that the number of different "cells" that you have divided the subspaces into is equal to $n \choose k$, since this counts the number of such strings of 0's and 1's. This is only the beginning of a rich interplay between combinatorics and geometry. The moral is that if you want to study an object with symmetries, you are very likely to encounter some interesting combinatorics along the way.