Matpic
mathematics, in pictures
Concept

Counting

Determining how many members a finite collection has without listing them. The two standard routes are a pairing with something already counted, and a decomposition into pieces whose counts add or multiply.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

Counting the colourings, by deleting and contracting. A graph beside the two smaller graphs its edge deletion and contraction produce, with the number of proper colourings of each at every number of colours up to 5.

Counting the colourings

Asking whether a graph can be coloured with four colours gives a yes or a no. Asking how many ways there are gives a polynomial — and the polynomial answers the first question, and several others nobody asked.

discrete · graph colouring The de Bruijn graph on 2 letters and words of 3, and the cycle through it. A graph whose vertices are short words and whose arrows are words one letter longer, with a closed walk using every arrow exactly once marked, and the cyclic sequence it spells.

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

computation · de bruijn

Named alongside it

The objects these essays reach for when they reach for this one.

Chromatic numberChromatic polynomialCyclic wordDe bruijn sequenceDeletion contractionEncodingEulerian circuitExhaustive searchGraphGraph colouringHierholzer's algorithmPolynomial

All concepts