A natural number greater than 1 is prime if it is divisible only by 1 and by itself.

A partition sequence of a finite simple graph G is a sequence of partitions of its vertex set that starts at the partition into singletons, merges two parts into one at every step, and ends at the partition with a single part. Two parts of a same partition are homogeneous if either every pair of vertices across them is adjacent or none is; two non-homogeneous parts are red-adjacent. The red degree of a part is the number of other parts of its partition that are red-adjacent to it.

The twin-width of G is the least d such that G has a partition sequence in which every part of every partition has red degree at most d.

A graph H is a depth-r minor of a graph G if H can be obtained from G by deleting vertices and edges and contracting pairwise disjoint connected subgraphs of radius at most r. A graph class is nowhere dense if for every depth r there is a t such that no member has the complete graph on t vertices as a depth-r minor.

The source lecture notes give these as Definitions 2.3 and 2.6 of Chapter 1 (2019/20 edition), writing H ⪯r G for the depth-r minor relation. Nowhere denseness is stated there as ωr(C) < ∞ for every r, with the excluded-clique form used here spelled out immediately after as an equivalent.

A word RAM is a random access machine whose writable memory consists of $2 ^ w$ cells holding natural numbers below $2 ^ w$. The word length $w$ is a parameter; one finite program serves all word lengths. Input is a read-only finite array supplied at initialization, also accessible as a sequential tape. Output is an append-only tape. Working memory starts at zero and output starts empty.

The input interface has four operations. $read a$ consumes the next entry of the sequential tape into cell $a$, halting if the tape is empty. $jeof l$ branches on tape emptiness without consuming input. $inputLength a$ writes the original input length into cell $a$. $inputLoad a b$ reads the original input at the index in cell $b$ into cell $a$, returning zero outside the input. Indexed access never consumes the sequential tape, and sequential reads never change the original input. Zero is ordinary data, not an end marker. Each operation costs one instruction. No length header or other framing is added to the supplied list.

Arithmetic results, input values and lengths, output values, and data-memory addresses are reduced modulo $2 ^ w$. Subtraction is truncated at zero, and division is integer division with $x / 0 = 0$. Input indices are words too. Program labels and the program counter are natural numbers and are not reduced modulo $2 ^ w$.