Combinatorics

For finite sets, removing the elements of

B

from

A

leaves

∣ A ∣ - ∣ A \cap B ∣

elements. Indeed

A

is the disjoint union of

A ∖ B

and

A \cap B

, so the rule of sum proves the formula. If

B \subseteq A

, it reduces to

∣ A ∖ B ∣ = ∣ A ∣ - ∣ B ∣

Chord diagram

A cyclically ordered collection of endpoints paired into chords of a circle. The crossing relation defines a circle graph; two chords with distinct endpoints cross exactly when their endpoints alternate.

Combinatorics on words

Inversion of a word

Word inversion number ( $inv (w)$ )

The number of inversions of a word: pairs of positions

i < j

with

w_{i} > w_{j}

. Unlike an inversion of a permutation, this definition permits repeated letters in the word.

Mechanical word

For slope

0 \leq α \leq 1

and intercept

ρ

, the lower mechanical word has letters

w_{n} = ⌊(n + 1) α + ρ ⌋ - ⌊ n α + ρ ⌋

. These letters are zero or one. Replacing floors by ceilings defines the upper mechanical word. An irrational slope gives a Sturmian word.

Lower mechanical word

The floor-based mechanical word

w_{n} = ⌊(n + 1) α + ρ ⌋ - ⌊ n α + ρ ⌋

Lyndon word

A nonempty finite word that is strictly smaller in lexicographic order than each of its nontrivial cyclic rotations. For example,

001

is a Lyndon word, whereas

010

is not because its rotation

001

is smaller.

Lyndon prefix

A prefix of a word that is itself a Lyndon word. The longest Lyndon prefix is useful when ranking necklaces and substrings of a De Bruijn sequence.

Polycube

A polycube is a face-connected union of finitely many unit cubes in the three-dimensional cubic grid. Its exposed square faces determine its surface area.

Unranking

Unranking constructs the object at a specified rank in a chosen ordering of a finite class. Lexicographic unranking uses lexicographic order.

Pólya enumeration

Pólya enumeration counts objects under a group action, often by applying the Pólya enumeration theorem to colourings.

Subset zeta transform ( $F (S) = \sum_{T \subseteq S} f (T)$ )

The subset zeta transform sends a function

f

on subsets to

F (S) = \sum_{T \subseteq S} f (T)

. For subsets of an

n

-element set, all values can be computed in

O (n 2^{n})

additions by processing one element at a time. Reversing containment gives the superset transform.

Pólya enumeration theorem

The Pólya enumeration theorem counts colourings up to a finite group action using the action's cycle index. Substituting colour weights into each cycle variable groups colourings by their colour inventories.

Entringer number ( $E (n, k)$ )

Entringer numbers refine counts of alternating permutations. One standard convention uses

E (0, 0) = 1

E (n, 0) = 0

for

n > 0

, and

E (n, k) = E (n, k - 1) + E (n - 1, n - k)

for

1 \leq k \leq n

. Reversed-row prefix sums generate the triangle.

Entringer triangle

The Entringer triangle arranges Entringer numbers into rows. Each row is obtained from reversed-row prefix sums, with the boundary convention specified by the recurrence.

Lexicographic unranking

Lexicographic unranking constructs the object at a specified position in lexicographic order. At each step it counts valid completions for each possible next symbol, skips blocks preceding the desired rank, and continues within the selected block.

Transfer matrix ( $T$ )

A transfer matrix stores the weights of allowed transitions between finitely many boundary states. Its powers sum weights of compatible sequences of transitions. For a cyclic boundary condition, the matrix trace

tr (T^{n})

counts weighted closed sequences of length

n

De Bruijn sequence

A cyclic sequence over an alphabet of size

q

in which every word of length

n

appears exactly once as a cyclic window. Its length is

q^{n}

. The De Bruijn graph converts its construction into an Eulerian cycle problem.

Binary De Bruijn sequence

Polyomino

A finite connected union of unit squares on the square lattice, joined along whole sides. Counting conventions may identify shapes under translation, rotation, or reflection, so those conventions must be specified.

Tromino

Combination (combinatorics)

A choice of

k

distinct elements from a set of

n

elements, with order ignored. Equivalently it is a

k

-element subset. The binomial coefficient

(k n)

counts such choices; choosing with repetition instead produces a multiset.

Allocation to labelled bins ( $N (n_{1}, \dots, n_{k}) = n! / (n_{1}! \dots n_{k}!)$ )

Allocate

n

distinct objects to

k

labelled bins of specified nonnegative sizes

n_{1}, \dots, n_{k}

, with

\sum_{i} n_{i} = n

. Order within a bin is ignored. The number of allocations is the multinomial coefficient

N (n_{1}, \dots, n_{k}) = \frac{n !}{n _{1} ! \dots n _{k} !} .

To prove this, order all the objects in a permutation and assign the first

n_{1}

to the first bin, the next

n_{2}

to the second, and so on. Every allocation comes from exactly

n_{1}! \dots n_{k}!

internal orderings. These disjoint classes exhaust the

n!

permutations, proving the formula by the multiplication principle. Empty bins are allowed because

0! = 1

For two bins of sizes

m

and

n - m

, the count is

(m n)

and every allocation has multiplicity

m! (n - m)!

in the permutation sample space. Exchanging two equal-sized labelled bins generally gives a different allocation. In contrast, a set partition uses unlabelled nonempty blocks; forgetting bin labels changes the counting problem and must not be done silently.

Pigeonhole principle ( $N > m ⟹ some box contains at least two objects$ )

Place

N

objects into

m \geq 1

boxes, assigning each object to exactly one box. Here

N

is a nonnegative integer and

m

is a positive integer. The pigeonhole principle says that if

N > m

, some box contains at least two objects. Equivalently, a function from an

N

-element finite set to an

m

-element finite set cannot be an injective function when

N > m

. The boxes may stand for categories rather than physical containers. ^[ref]

For thirteen objects and twelve boxes, a box containing at least two is unavoidable. Thinking of thirteen people and their birth months gives the same conclusion: at least two share a birth month. Twelve people could occupy the twelve months one apiece, so thirteen is the smallest number that forces a shared month. The generalized pigeonhole principle quantifies how many objects must share a box when there are still more objects.

The useful surprise is that the pigeonhole principle proves existence without needing to locate the objects involved. Choosing a good assignment rule is often the creative step: equal labels can mean equal remainders, nearby points, or repeated states of an algorithm. Once the rule is chosen, a short count can force a relationship among a much larger collection of objects. The pigeonhole principle itself does not name the crowded box. When the objects and their assignments are explicitly available, a simple algorithm finds one: scan the objects, keep the first object seen in each box, and stop when a later object enters an occupied box. At most

m + 1

scanned objects are needed when

N > m

A geometric example. Any five points in a square of side one contain two whose Euclidean distance is at most

1/ 2

. Give each point Cartesian coordinates

(x, y) \in [0, 1]^{2}

. Divide both ranges into the intervals

[0, 1/2)

and

[1/2, 1]

, making four cells. Thus

x < 1/2

belongs to the left half and

x \geq 1/2

to the right half;

y < 1/2

belongs to the lower half and

y \geq 1/2

to the upper half. This convention assigns every boundary point to exactly one cell.

The pigeonhole principle puts two of the five points in the same cell. Their differences in Cartesian coordinates have magnitude at most

1/2

, so the Pythagorean theorem gives their Euclidean distance

d

the bound

d^{2} \leq (\frac{1}{2})^{2} + (\frac{1}{2})^{2} = \frac{1}{2}, d \leq \frac{1}{2} \approx 0.707107.

For the plotted points

(0.1, 0.1)

(0.4, 0.4)

(0.8, 0.2)

(0.2, 0.8)

and

(0.8, 0.8)

, the first two occupy the lower-left cell and have Euclidean distance

0. 3^{2} + 0. 3^{2} = 0.18 \approx 0.424264

. These Cartesian coordinates exhibit the forced pair; the argument applies to every placement of five points.

Figure 1.
The pigeonhole principle places two of five points in one of four cells of a square, bounding their Euclidean distance by $1/ 2$
. **Details**.

An arithmetic example. Assign eight integers to their seven residue classes modulo the integer modulus

7

. The pigeonhole principle gives two with the same residue class, so

7

is an integer divisor of their difference. In

{2, 5, 9, 12, 16, 20, 24, 27}

, for example,

2

and

9

satisfy the integer congruence

9 \equiv 2 (mod 7)

, and

9 - 2 = 7

. Likewise, assigning fractional parts to short intervals gives the Dirichlet approximation theorem; its existing article explains the approximation bound.

Consecutive sum divisible by the sequence length ( $\exists 0 \leq i < j \leq n : n ∣ \sum_{k = i + 1}^{j} a_{k}$ )

For any sequence of

n \geq 1

integers, some nonempty consecutive block has sum divisible by

n

. Form the

n + 1

prefix sums

s_{0} = 0, s_{j} = \sum_{k = 1}^{j} a_{k}

. There are only

n

residue classes modulo

n

, so the pigeonhole principle gives

s_{i} \equiv s_{j} (mod n)

for some

i < j

. Subtraction proves that

s_{j} - s_{i}

is the required block sum. Negative entries and repeated entries cause no difficulty. Applied after any ordering of a finite set, it also gives a nonempty subset whose sum is divisible by the size of the set.

Pigeonhole distance bound from a partition ( $m + 1 points in m sets of diameter \leq D ⟹ d (x_{i}, x_{j}) \leq D$ )

Suppose a subset of a metric space is covered by

m

sets, each of diameter at most

D

. Assign each point to one covering set containing it, choosing a single set at shared boundaries. Among

m + 1

points, the pigeonhole principle puts two in a common set, and their distance is at most

D

. The pieces need not be equal or congruent. This freedom permits better distance bounds than dividing a region only into equal rectangles.

Generalized pigeonhole principle ( $max_{i} n_{i} \geq ⌈ N / m ⌉$ )

For

N

objects assigned to

m \geq 1

boxes, let

n_{i}

be the number in box

i

. The generalized pigeonhole principle states

n_{1} + \dots + n_{m} = N ⟹ max_{1 \leq i \leq m} n_{i} \geq ⌈ \frac{N}{m} ⌉ .

The ceiling function rounds up because box counts are integers. An equivalent threshold formulation says: for a positive integer

k

, if

N > m (k - 1)

, some box contains at least

k

objects. For

N = m (k - 1)

, putting

k - 1

objects in each box shows why the strict inequality matters. ^[ref]

Computed examples. For

N = 13

and

m = 12

⌈ 13/12 ⌉ = 2

. Counts

(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

attain this bound. For

N = 23

and

m = 7

⌈ 23/7 ⌉ = 4

, and the balanced counts

(4, 4, 3, 3, 3, 3, 3)

sum to

23

and have largest count exactly

4

. The threshold version agrees:

23 > 7 (4 - 1) = 21

. In contrast, seven boxes each containing three hold only

21

objects.

The bound is sharp for every

N

and

m

. Use Euclidean division to write

N = q m + r

with integers

q \geq 0

and

0 \leq r < m

. Place

q + 1

objects in each of

r

boxes and

q

objects in each remaining box. The largest count is

q + 1

r > 0

, and

q

r = 0

, exactly

⌈ N / m ⌉

. This balanced arrangement makes the guarantee best possible even though other arrangements can be much more crowded.

Proof outline. If every count were at most

k - 1

, the total would be at most

m (k - 1)

. This contradicts

N > m (k - 1)

. Taking

k = ⌈ N / m ⌉

proves the displayed bound for

N > 0

; for

N = 0

every count is zero.

Infinite pigeonhole principle

The infinite pigeonhole principle says that if an infinite set has a partition of a set into finitely many parts, at least one part is an infinite set. Equivalently, assigning infinitely many objects to a finite number of boxes forces some box to contain infinitely many objects. For example, separating the natural numbers into their two residue classes modulo

2

forces at least one class to be an infinite set; here both are, as the lists

0, 2, 4, \dots

and

1, 3, 5, \dots

show.

Proof outline. A union of finitely many finite sets is a finite set. If all the parts were finite sets, their union could not be the original infinite set.

The assumption of finitely many parts is essential. With one box labelled by each natural number, assigning

n

to box

n

puts exactly one object in every box. Infinitely many objects and infinitely many boxes therefore need not produce even a shared box. The infinite pigeonhole principle is useful whenever finitely many labels organize an endless collection: one label must keep occurring infinitely often, providing an infinite set on which that label is constant.

Enumerative combinatorics

q-analogue

A parameter-dependent generalization which recovers a familiar object at a specified value or limit of the parameter. In enumerative combinatorics, a generating function can refine an ordinary count by retaining a statistic; Gaussian binomial coefficients are one example.

Board tiling

Covering a finite board with specified tiles without gaps or overlaps. Counting board tilings connects local placement rules to a recurrence relation and a generating function.

Combinatorial structure

Labelled combinatorial structure

A combinatorial structure whose elements carry distinct labels from a prescribed finite set. For example, a rooted tree can have labelled vertices; assigning labels is part of the structure counted by an exponential generating function.

Independence system ( $(E, I)$ )

An independence system consists of a finite set

E

and a nonempty family

I

of subsets such that

I \in I

and

J \subseteq I

imply

J \in I

. This is the hereditary condition: deleting chosen elements keeps a selection admissible. In particular, the empty set belongs to

I

. An independence system becomes a matroid when it also satisfies the matroid independence axioms for exchange. The hereditary nonmatroid greedy obstruction shows why deletion alone does not justify a greedy algorithm.

Ground set ( $E$ )

The ground set is the set of labelled elements available for selection. An independence system specifies which subsets of this ground set are admissible; in a linear matroid the labels index vectors, whereas in a graphic matroid they index edges.

Hereditary nonmatroid greedy obstruction

On the ground set

E = {x, y, z}

, permit exactly

F = {\emptyset, {x}, {y}, {z}, {y, z}}, w (x) = 10, w (y) = w (z) = 6.

This lists every admissible subset; the excluded subsets are

{x, y}

{x, z}

, and

{x, y, z}

. It is an independence system: deleting elements from

{y, z}

produces its listed singletons or the empty set, and deleting from a singleton produces the empty set. But

I = {x}

and

J = {y, z}

violate exchange: neither

y

nor

z

can be added to

I

. Thus it is not a matroid.

The descending-weight greedy algorithm admits

x

first, then rejects both

y

and

z

, returning

{x}

with weight

10

. Exchanging the tied order of

y, z

changes nothing. The admissible pair

{y, z}

weighs

12

, exceeding every singleton and the empty set, so it is the true optimum. Both

{x}

and

{y, z}

are maximal elements under inclusion of subsets, but only the pair has maximum cardinality. This identifies exactly where the matroid greedy algorithm loses its guarantee: heredity preserves admissibility under deletions, while exchange prevents a locally maximal selection from being too small.

Matroid

A matroid is an independence system in which a smaller admissible selection can always grow using an element of a larger admissible selection. This exchange rule abstracts linear independence of vectors and the selection of edges forming a forest. It forces all matroid bases to have the same cardinality and makes the matroid greedy algorithm correct for maximizing their total weight. The useful surprise is that local choices become globally optimal because of a structural rule about admissible subsets, rather than a special numerical coincidence.

The weighted three-vector matroid below lets us inspect every subset and every possible size comparison. Its three vectors give three two-element matroid bases, yet their total weights differ. The graphic matroid of a graph triangle has exactly the same admissible labels. A pregeometry is a finitary closure-theoretic extension to possibly infinite sets.

Matroid independence polytope ( $P_{I} (M) = {x \geq 0 : x (A) \leq r_{M} (A) for all A \subseteq E}$ )

For a finite matroid

M = (E, I)

, the convex hull of the indicator vectors of its matroid independent sets is exactly the displayed system, where

x (A) = \sum_{e \in A} x_{e}

. It is an integral polytope. The equality

x (E) = r_{M} (E)

instead gives the face corresponding to matroid bases; independence does not require that equality.

Proof. If

I

is independent,

∣ I \cap A ∣ \leq r_{M} (A)

, so every independent indicator and every convex combination of them satisfies the inequalities. For the reverse inclusion, take an arbitrary real objective

c

. List its positive coordinates in nonincreasing order as

c_{1} \geq \dots \geq c_{k} > 0

, put

c_{k + 1} = 0

and let

S_{i}

be the first

i

elements in this ordering. Run the matroid greedy algorithm on these elements, obtaining an independent set

I

. At every prefix the selected elements are maximal in

S_{i}

: an earlier rejected element cannot become admissible after further additions, by heredity. The augmentation axiom implies that every maximal independent set in

S_{i}

has size

r_{M} (S_{i})

. Hence

∣ I \cap S_{i} ∣ = r_{M} (S_{i})

For every point satisfying the displayed system, nonnegativity and telescoping give

c^{T} x \leq \sum_{j = 1}^{k} c_{j} x_{e_{j}} = \sum_{i = 1}^{k} (c_{i} - c_{i + 1}) x (S_{i}) \leq \sum_{i = 1}^{k} (c_{i} - c_{i + 1}) r_{M} (S_{i}) = c^{T} 1_{I} .

Thus every linear objective is maximized by an independent indicator, with the empty set used if all coefficients are nonpositive. Singleton rank inequalities bound every coordinate between zero and one, making the system compact. If it contained a point outside the compact convex hull of independent indicators, the finite-dimensional separating hyperplane theorem would supply an objective strictly larger at that point than at every independent indicator, a contradiction. This proves equality and integrality without assuming the desired convex-hull description in advance. Negative objective coefficients are discarded explicitly; maximizing over independent sets differs from maximizing over bases when such coefficients occur.

Forest polytope ( $conv {1_{F} : (V, F) is a forest}$ )

For an undirected finite graph, its forest polytope is the matroid independence polytope of its graphic matroid. It has the exact inequality descriptions

{x \geq 0 : x (A) \leq ∣ V ∣ - κ (V, A) for all A \subseteq E} = {x \geq 0 : x (E (S)) \leq ∣ S ∣ - 1 for all nonempty S \subseteq V} .

Here

κ (V, A)

counts all connected components of a graph, including isolated vertices, and

E (S)

denotes the edges internal to

S

. A maximal forest has one fewer edge than vertices in each component, giving the rank

∣ V ∣ - κ (V, A)

. The matroid independence polytope theorem therefore proves the first description. It implies the second since the rank of

E (S)

is at most

∣ S ∣ - 1

. Conversely, split any

A

into its vertex components

S_{j}

; nonnegativity gives

x (A) \leq \sum_{j} x (E (S_{j})) \leq \sum_{j} (∣ S_{j} ∣ - 1) = ∣ V ∣ - κ (V, A)

. No spanning requirement is imposed, so an optimum with negative edge weights can leave vertices isolated.

Small matroid enumeration

On labelled ground sets of sizes

1, 2, 3

, there are respectively

2, 5, 16

matroids, or

2, 4, 8

up to matroid isomorphism. At rank of a matroid one, a nonempty subset of nonloops specifies all matroid independent sets of cardinality one. On three labels at rank of a matroid two, the three types are one matroid loop with an independent pair, no matroid loops with one pair of parallel elements of a matroid, and all pairs independent with the triple dependent.

Matroid closure exchange property ( $y \in / cl_{M} (A), y \in cl_{M} (A + x) \Rightarrow x \in cl_{M} (A + y)$ )

The closure of a matroid obeys the displayed exchange rule. This is the finite pregeometry exchange principle: if adding

x

newly makes

y

dependent, then adding

y

also makes

x

dependent.

Proof. Write

r = r (A)

. The first hypothesis and the one-element bound on the rank of a matroid give

r (A + y) = r + 1

. The second gives

r (A + x + y) = r (A + x) \leq r + 1

. Inclusion gives

r (A + x + y) \geq r (A + y)

, so equality holds. This is exactly

x \in cl_{M} (A + y)

Closure of a matroid ( $cl_{M} (A) = {x : r (A \cup {x}) = r (A)}$ )

The closure of a matroid adds all elements that fail to increase its rank of a matroid. It abstracts the linear span in a linear matroid. It is extensive, preserves inclusion, preserves the rank of a matroid, and is an idempotent function:

A \subseteq cl_{M} (A), A \subseteq B \Rightarrow cl_{M} (A) \subseteq cl_{M} (B), r (cl_{M} (A)) = r (A), cl_{M} (cl_{M} (A)) = cl_{M} (A) .

Proof. Extensivity follows from

A + x = A

when

x \in A

. If

A \subseteq B

and

x \in / B

, submodularity of matroid rank gives

r (B + x) - r (B) \leq r (A + x) - r (A)

. Thus an element in

cl_{M} (A)

also lies in

cl_{M} (B)

; the case

x \in B

is automatic. Add the finitely many elements of

cl_{M} (A) ∖ A

one at a time. Inclusion preservation makes each addition have zero marginal increment of the rank of a matroid, proving rank preservation.

For completeness, nested subsets

A \subseteq B

of equal rank of a matroid have the same closure of a matroid. If

x \in / B

, apply submodularity of matroid rank to

B

and

A + x

to obtain

r (B + x) \leq r (A + x)

; monotonicity gives the reverse bound. The defining tests for membership in their closures are therefore equal. If

x \in B

r (A) \leq r (A + x) \leq r (B) = r (A)

, so both closures contain

x

. Apply this equal-rank result to

A \subseteq cl_{M} (A)

to prove idempotence. In particular, every maximal matroid independent set of

B

has the same closure of a matroid as

B

Uniform matroid ( $U_{r, n}$ )

For

0 \leq r \leq n

, the uniform matroid

U_{r, n}

on an

n

-element ground set has as its matroid independent sets exactly the subsets of cardinality at most

r

. Heredity is immediate, and augmentation works because any smaller such subset can acquire an element of a larger one without exceeding

r

. Its rank of a matroid on

A

min {∣ A ∣, r}

Parallel elements of a matroid ( $r ({x}) = r ({y}) = r ({x, y}) = 1$ )

Distinct nonloops

x, y

are parallel elements of a matroid when their pair is dependent. Declaring each nonloop parallel to itself makes parallelism an equivalence relation on the nonloops. Transitivity follows directly from augmentation: if

{a, b}

and

{b, c}

are dependent but

{a, c}

independent, the independent singleton

{b}

could not be augmented from the independent pair

{a, c}

, contradicting the matroid independence axioms. In a linear matroid, nonzero proportional vectors give parallel elements of a matroid.

Dependent set of a matroid ( $D \in / I$ )

A matroid dependent set is a subset of the ground set that is not a matroid independent set. By heredity, every subset containing a matroid dependent set is also dependent. Distinct nonloops are parallel elements of a matroid exactly when their pair is a matroid dependent set.

Nonloop of a matroid ( $r ({x}) = 1$ )

A nonloop is an element whose singleton is a matroid independent set. It is precisely an element that is not a loop of a matroid, and its singleton has rank of a matroid one.

Loop of a matroid ( $r ({x}) = 0$ )

An element

x

is a loop of a matroid when its singleton is not a matroid independent set. By heredity, no matroid independent set contains it. Equivalently its singleton has rank of a matroid zero, or it belongs to the closure of a matroid of the empty set. In a graphic matroid, a self-loop is a loop of a matroid.

Matroid isomorphism ( $ϕ : E \to E^{'}$ )

A matroid isomorphism between

(E, I)

and

(E^{'}, I^{'})

is a bijection

ϕ

such that

I \in I

if and only if

ϕ (I) \in I^{'}

. It relabels the ground set without changing independence. The number of labelled matroids therefore differs from the number of types up to matroid isomorphism.

Matroid independence axioms ( $M = (E, I)$ )

Let

E

be a finite set and

I \subseteq P (E)

a family of subsets, where

P (E)

is the power set. The matroid independence axioms are

\emptyset \in I, I \in I, J \subseteq I ⟹ J \in I, I, J \in I, ∣ I ∣ < ∣ J ∣ ⟹ \exists e \in J ∖ I : I \cup {e} \in I .

The second condition is heredity; the third is exchange, also called augmentation. The set difference

J ∖ I

matters: the new element must actually increase the cardinality of

I

. Exchange adds one element without requiring any deletion from

I

. Nonemptiness together with heredity is equivalent to the first condition. ^[ref]

Independent set of a matroid ( $I \in I$ )

A matroid independent set is a subset belonging to the family

I

. Independence refers to the chosen matroid: for a linear matroid it means linear independence, and for a graphic matroid it means that the chosen edges contain no graph cycle. It is different from an independent set, which selects vertices with no edge between them.

Basis of a matroid ( $B$ )

A matroid basis is a matroid independent set that is a maximal element under inclusion of subsets: no additional element of the ground set can be admitted. Maximum cardinality means having the largest size among all matroid independent sets. Maximality tests whether this particular selection can grow; maximum size compares it with every selection. In a matroid the two conditions coincide, so all matroid bases have a common size. They need not have equal weight. ^[ref]

Proof outline. If a maximal matroid independent set

B

were smaller than another matroid independent set

J

, the matroid independence axioms would admit an element of

J ∖ B

, contradicting maximality. Finiteness allows every matroid independent set to grow to a matroid basis by successive admissible additions. In a general independence system, maximal selections can have different sizes, as in the hereditary nonmatroid greedy obstruction.

Rank of a matroid ( $r_{M} (A)$ )

For a subset

A

of the ground set, the rank of a matroid on

A

is the maximum cardinality of a matroid independent set contained in

A

r_{M} (A) = max {∣ I ∣ : I \subseteq A, I \in I} .

Thus

r_{M} (E)

is the common size of the matroid bases, and

r_{M} (\emptyset) = 0

. The weighted three-vector matroid has

r_{M} (E) = 2

, even though its ground set has three labels.

Submodular rank function ( $r : 2^{E} \to Z_{\geq 0}$ )

On a finite ground set

E

, a submodular rank function is a normalised set function

r

with

r (\emptyset) = 0

, a monotone set function, and a submodular set function, such that

r (A \cup {e}) - r (A) \in {0, 1}

for

e \in / A

. Equivalently, require nonnegative integer values, monotonicity, submodularity and

r ({e}) \leq 1

. The diminishing returns characterization of submodularity bounds each marginal by its singleton value. Thus

0 \leq r (A) \leq ∣ A ∣

These functions are precisely the rank functions of matroids. To see the converse direction, define

I = {A : r (A) = ∣ A ∣}

. It contains the empty set. If

B \subseteq A \in I

, the unit marginal bounds give

∣ A ∣ = r (A) \leq r (B) + ∣ A ∖ B ∣

, so

r (B) = ∣ B ∣

and heredity holds. For augmentation, suppose

A, B \in I

with

∣ A ∣ < ∣ B ∣

. If every

e \in B ∖ A

had zero marginal over

A

, diminishing returns would keep each marginal zero as they are added successively. This would give

r (A \cup B) = r (A) = ∣ A ∣ < ∣ B ∣ = r (B)

, contradicting monotonicity. Some marginal is therefore one, giving an independent augmentation.

Finally any inclusion-maximal

I \subseteq A

in this independence family has

r (I \cup {e}) = r (I)

for every remaining

e \in A ∖ I

. Successively adding them and using diminishing returns shows

r (A) = r (I) = ∣ I ∣

, so the resulting matroid really has rank

r

. The forward direction is submodularity of matroid rank. These integer increment conditions distinguish matroid ranks from arbitrary real-valued submodular functions.

Submodularity of matroid rank ( $r (A) + r (B) \geq r (A \cap B) + r (A \cup B)$ )

The rank of a matroid is a normalised set function, a monotone set function, and a submodular set function. Adding one element increases it by at most one.

Proof of submodularity. Choose a maximal matroid independent set

I_{0}

A \cap B

, extend it to a maximal matroid independent set

I_{A}

A

, then extend it to one

I_{U}

A \cup B

. The matroid independence axioms make their sizes

r (A \cap B)

r (A)

and

r (A \cup B)

. Every element of

I_{U} ∖ I_{A}

lies outside

A

, since otherwise it could be added to

I_{A}

inside

A

. Hence

I_{0} \cup (I_{U} ∖ I_{A})

is an independent subset of

B

, so its size

r (A \cap B) + r (A \cup B) - r (A)

is at most

r (B)

The remaining assertions follow from the definition of the rank of a matroid. The empty set has maximum independent size zero, increasing the available subset cannot reduce that maximum, and deleting a newly added element from an independent subset decreases its size by at most one.

Linear matroid

A linear matroid has a finite ground set indexing a family of vectors in a vector space over a specified field. A subset of labels is a matroid independent set precisely when its vectors are linearly independent. Labels distinguish repeated vectors; the ground set is not required to consist of distinct numerical vectors. The matroid bases correspond to bases for the linear span of all the supplied vectors.

Exchange outline. The linear span of

∣ I ∣

linearly independent vectors has dimension

∣ I ∣

. If

∣ J ∣ > ∣ I ∣

, not all the linearly independent vectors indexed by

J

can lie in that linear span. A vector outside it can be added to

I

. Heredity follows because a linear dependence in a subset would also be a linear dependence in the full selection.

Weighted three-vector matroid

Take labels

E = {a, b, c}

and vectors in the real vector space

R^{2}

v_{a} = (1, 0), v_{b} = (0, 1), v_{c} = (1, 1), w (a) = 8, w (b) = 5, w (c) = 6.

Here is the complete independence check for all eight subsets. The empty set is independent. Each of

{a}, {b}, {c}

is independent because its vector is nonzero. Every pair is independent: the determinants of the two-column matrices

[v_{a} v_{b}]

[v_{a} v_{c}]

, and

[v_{b} v_{c}]

are respectively

1

1

, and

- 1

. The triple is dependent because

v_{c} - v_{a} - v_{b} = 0

. Therefore

I = {\emptyset, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}} .

Deleting elements from any listed subset stays in this list, verifying heredity. Every exchange comparison has sizes

(0, 1)

(0, 2)

, or

(1, 2)

. From the empty set, any element of the larger matroid independent set works: this covers three singleton targets and three pair targets. From any singleton to any pair, every element of the pair outside the singleton works, since every resulting pair is independent. This covers all nine singleton-pair comparisons, including disjoint ones. There are no other comparisons: all fifteen ordered size-increasing pairs satisfy exchange.

Figure 1.
Three vectors have three independent pairs and one dependent triple; the heaviest matroid basis is ${a, c}$ with weight $14$
. **Details**.

The three matroid bases are

{a, b}

{a, c}

, and

{b, c}

, all of cardinality two, with weights

13

14

, and

11

. The matroid greedy algorithm considers

a

, then

c

, then

b

: it admits

a

, admits

c

because their determinant is nonzero, and rejects

b

because the triple is dependent. The resulting matroid basis

{a, c}

has weight

8 + 6 = 14

, the largest of the three totals. Every singleton can grow, so none is maximal; the three pairs are both maximal and maximum in cardinality.

Graphic matroid

For a finite undirected graph, the graphic matroid has its edges as the ground set. A subset is a matroid independent set when its edges form a forest on the original vertices, including isolated vertices. Its matroid bases give a spanning tree in each connected component of a graph; for a connected graph, each matroid basis is a spanning tree.

For a graph triangle on vertices

P, Q, R

, label the edges

a = PQ

b = QR

, and

c = PR

, with weights

8, 5, 6

. The empty set, all singletons, and all pairs are forests; the triple contains the graph cycle

P, Q, R, P

. Thus its eight subsets have exactly the independence pattern checked in the weighted three-vector matroid, and the same fifteen exchange comparisons pass. The matroid greedy algorithm chooses

PQ

, chooses

PR

, and rejects

QR

, producing the heaviest spanning tree, of weight

14

Figure 1.
A weighted graph triangle admits greedy selection of a matroid basis; a hereditary independence system without exchange traps a greedy algorithm at weight $10$ instead of $12$
. **Details**.

Exchange outline. Deleting edges cannot create a graph cycle. If forests

I, J

have

∣ I ∣ < ∣ J ∣

, some edge of

J

joins different connected components of a graph of

I

: otherwise, within each such component,

J

would have at most its number of vertices minus one edges, giving

∣ J ∣ \leq ∣ I ∣

. Adding that edge keeps a forest. This is the matroid independence axioms expressed through connectivity.

Matroid greedy algorithm ( $w (B) = \sum_{e \in B} w (e)$ )

Assign each element of the finite ground set a real number

w (e)

. The matroid greedy algorithm sorts elements by nonincreasing weight, starts with the empty set, and admits an element exactly when the enlarged selection is a matroid independent set. Ties can be resolved arbitrarily. After all elements have been considered, the result is a matroid basis of maximum total weight among all matroid bases. This holds even with negative weights: the task is to produce a full matroid basis. ^[ref]

Maximizing weight over all matroid independent sets is a different task when weights can be negative. For that task, skip negative elements; zero-weight additions are optional. With weights

w (a) = 8

w (c) = - 1

w (b) = - 2

in the weighted three-vector matroid, the heaviest matroid basis is

{a, c}

with weight

7

, while the heaviest matroid independent set is

{a}

with weight

8

. For nonnegative weights, every matroid independent set can be extended to a matroid basis without reducing weight, so the optimum values coincide.

Proof outline. Let

g_{1}, \dots, g_{r}

be the admitted elements in order, and order any competing matroid basis

b_{1}, \dots, b_{r}

by nonincreasing weight. If

w (b_{k}) > w (g_{k})

, exchange would let one of

b_{1}, \dots, b_{k}

augment

{g_{1}, \dots, g_{k - 1}}

. That element was considered before

g_{k}

and, by heredity, was admissible even at that earlier stage, a contradiction. Hence

w (g_{k}) \geq w (b_{k})

for every

k

, and summing proves optimality. Rejected elements remain inadmissible as the selection grows, by heredity, so the final selection is maximal. The guarantee depends on the matroid independence axioms and on weights adding independently across elements; interactions between chosen elements are a different objective.

Rule of product ( $∣ A_{1} \times \dots \times A_{k} ∣ = \prod_{j = 1}^{k} ∣ A_{j} ∣$ )

For finite sets, the number of ordered choices of one element from each is the product of the individual numbers of choices. More generally, if stage

j

has exactly

n_{j}

possible choices after every permitted history of earlier stages, the total number of full choice sequences is

\prod_{j} n_{j}

, by mathematical induction on the stages. This counts

b^{a}

functions between sets of sizes

a, b

, and counts the injective functions by the falling factorial

b (b - 1) \dots (b - a + 1)

when

a \leq b

With five people, choose a captain in five ways and a different deputy in four ways: $5 \cdot 4 = 20$ ordered assignments. The second choice depends on the first because the captain is excluded, but its number of permitted options is always four. The rule of product therefore applies without any assumption about independent events. To count two-person teams instead, each subset has two possible role assignments, so division by

2! = 2

gives ten teams. This division works because every team was counted equally often.

Addition principle ( $∣ A ⊔ B ∣ = ∣ A ∣ + ∣ B ∣$ )

The rule of sum counts alternatives in disjoint finite sets by adding their sizes. For a disjoint union

A ⊔ B

, each element belongs to exactly one alternative, so

∣ A ⊔ B ∣ = ∣ A ∣ + ∣ B ∣

. Overlapping alternatives require accounting for repeated elements, as in the inclusion-exclusion principle. The groups indexed by first-return position in the Catalan recurrence are disjoint alternatives.

Steiner system ( $S (t, k, v)$ )

A Steiner system

S (t, k, v)

is a

v

-point set with

k

-point blocks such that every

t

-point subset is contained in exactly one block. Necessarily the number of blocks is

(t v) / (t k)

. This count is a necessary consistency check, not a substitute for proving exact containment. The small Witt design is

S (5, 6, 12)

Block of a Steiner system

A designated subset in a Steiner system is a Steiner block. In a system

S (t, k, v)

, each Steiner block contains

k

points and each

t

-point subset belongs to exactly one Steiner block. For

t = 2

, this is the pair-coverage condition used in a cyclotomic construction of a Steiner 2-design.

Difference family for a Steiner 2-design

In a finite additive group, a family of

k

-subsets is a difference family of index one if each nonzero group element occurs exactly once among all their ordered within-block differences. Translating its Steiner blocks by every group element gives a Steiner system with parameters

2

(v, k, 1)

: the unique representation of a difference determines the unique translated Steiner block through two specified points.

Cyclotomic construction of a Steiner 2-design

Put

m = (2 k)

, take odd

q \equiv 1 (mod 2 m)

, and let

H

be the index-

m

multiplicative subgroup. If a

k

-set

A

has its unordered pair differences in distinct

H

-cosets, choose

S \subset H

containing exactly one element from each pair

{h, - h}

. Then

{s A : s \in S}

is a difference family for a Steiner 2-design. Indeed one unordered pair supplies each coset, and its two difference orientations multiplied by

S

cover that coset once. Translations yield a

2

(q, k, 1)

Steiner system. The cyclotomic pattern extension by a second-moment bound supplies suitable

A

for all sufficiently large

q

in this progression.

Small Witt design ( $S (5, 6, 12)$ )

The small Witt design is a Steiner system

S (5, 6, 12)

with 132 blocks. A six-set duad-syntheme duality constructs it on two disjoint six-sets: two whole-half blocks, forty-five blocks of each of the types

(2, 4)

and

(4, 2)

, and forty corresponding-partition blocks of type

(3, 3)

. The internal-duad/cross-syntheme incidence rule proves that each five-set lies in exactly one of these blocks.

Synthematic construction of the small Witt design

On a six-point set

X

and its six totals of synthemes

Y

, each duad determines a partition of

Y

into three pairs according to their shared synthemes. Include both whole halves, the 45 blocks

D \cup (Y ∖ P)

for these duad-pair incidences, and their complements. For each partition

X = A ⊔ A^{c}

into triples, cross synthemes give two triangular components on

Y

; include the four unions of a part of

X

with a component. These 132 blocks form the small Witt design.

Six-point matching geometry

The complete graph on six points has fifteen edges and fifteen perfect matchings. Its six one-factorizations organize a dual incidence geometry exchanging points with factorizations and edges with matchings. The classical names are duads, synthemes and totals of synthemes. This geometry supports duad-syntheme duality on six points and a construction of the small Witt design.

Pentad construction of the exceptional alternating-group automorphism

The six pentads are the six one-factorizations of the complete graph on six points. Permuting the ground-set points permutes these factorizations. The action sends a transposition to three disjoint transpositions and a

3

-cycle to two disjoint

3

-cycles. Its restriction to

A_{6}

is faithful by simplicity, and the full action of

S_{6}

is faithful because an order-two kernel would be central. It is consequently an automorphism of

S_{6}

. Its restriction preserves

A_{6}

and changes

3

-cycle type, so it cannot be induced on

A_{6}

by any conjugation from

S_{6}

Duad-syntheme duality on six points

A bijection from the points of one six-set to the totals of another extends by incidence to bijections from duads to synthemes, synthemes to duads, and totals to points. A duad maps to the intersection of its two point-totals. The same duality exchanges internal duads of a three-versus-three partition with cross synthemes of its corresponding partition. The latter rule follows by splitting the six cross perfect matchings into parity classes of three, yielding two triangles on the six totals.

Duad

A duad is an unordered pair of distinct points. On a six-point set there are

(2 6) = 15

duads. They are the edges of the complete graph and are grouped into synthemes.

Syntheme

A syntheme partitions six points into three duads, equivalently a perfect matching of the complete graph. There are

6! / (2^{3} 3!) = 15

synthemes. Every duad belongs to three. Two edge-disjoint synthemes extend to a unique total of synthemes: their union is a six-cycle, whose complement has a unique factorization into three matchings.

Total of synthemes

A total is a set of five edge-disjoint synthemes covering all fifteen duads of a six-point set. There are six totals; each syntheme belongs to two and every two totals share exactly one syntheme. Each total contains exactly one syntheme containing any prescribed duad. Totals are one-factorizations of the complete graph.

Counting synthematic totals

Two disjoint synthemes form a six-cycle, whose complement is a triangular prism. The prism has a unique partition into three perfect matchings, so the pair extends uniquely to a total of synthemes. Eight synthemes are disjoint from a fixed syntheme; grouping them four per total yields two totals through it, and double counting gives six totals in all.

// Target: combinatorics.bigb

Cycle lemma ( $\sum_{i} b_{i} = 1$ )

The cycle lemma turns a constraint at every prefix into a choice of where to start reading a circular sequence. Think of a lattice path whose vertical increments record votes for two candidates:

+ 1

for one candidate and

- 1

for the other. Its partial sums are the running lead. Rotating the increments preserves the final lead, but changes whether that lead stays strictly positive throughout. This makes rotation useful for counting lattice paths subject to prefix constraints; the sum-one cycle lemma also supplies the cyclic prefix condition in the cyclic Turán covering construction.

The sum-one form. Let

b = (b_{1}, \dots, b_{n})

be any nonempty sequence of integers with

\sum_{i = 1}^{n} b_{i} = 1

. A starting position

r \in {0, \dots, n - 1}

means reading the rotated sequence

b^{(r)} = (b_{r + 1}, \dots, b_{n}, b_{1}, \dots, b_{r}) .

Call

r

good when every nonempty partial sum of

b^{(r)}

is strictly positive, including the full sum:

P_{j}^{(r)} = \sum_{i = 1}^{j} b_{i}^{(r)} > 0 (1 \leq j \leq n) .

The cycle lemma says there is exactly one good starting position. Negative entries, zero entries and positive entries larger than one are all allowed in this sum-one form. The empty partial sum is zero and is excluded from the positivity requirement. Douglas West's exercise 1.3.46(a) states a stronger result for arbitrary integer entries: take its case with all

n

partial sums positive. ^[ref]

A worked sum-one example. For

b = (2, - 2, 0, 1)

, the partial sums starting at zero are

S_{0}, S_{1}, S_{2}, S_{3}, S_{4} = 0, 2, 0, 0, 1

. Starts

0, 1, 2

fail: they have, respectively, a zero second partial sum, a negative first partial sum, and a zero first partial sum. Start

3

reads

(1, 2, - 2, 0)

and has nonempty partial sums

1, 3, 1, 1

, all positive. This example both allows an increment larger than one and shows why touching zero fails.

Why the last minimum works. Put

S_{0} = 0

and

S_{j} = \sum_{i = 1}^{j} b_{i}

. Choose the last index

r

attaining the minimum of the proper partial sums

S_{0}, \dots, S_{n - 1}

: include

S_{0}

and exclude

S_{n}

. After that index, later proper partial sums are strictly larger than

S_{r}

; also

S_{n} = 1 > S_{r}

, since

S_{r} \leq 0

. Before wrapping, the new partial sums are therefore positive differences

S_{j} - S_{r}

. After wrapping, they are

1 + S_{j} - S_{r} \geq 1

. In the worked example the last minimum is at

r = 3

; choosing the first minimum at

r = 0

would fail. Uniqueness takes one further observation: two good starts would split the circle into two nonempty arcs, each having a positive integer sum, yet their sum would be one.

Cycle lemma with increments at most one ( $# {good starting positions} = k$ )

A standard positive-total form of the Dvoretzky-Motzkin cycle lemma uses a nonempty sequence

a = (a_{1}, \dots, a_{n})

of integers satisfying

a_{i} \leq 1 (1 \leq i \leq n), \sum_{i = 1}^{n} a_{i} = k > 0.

Exactly

k

starting positions have every nonempty partial sum strictly positive, using the same rotation convention as the sum-one cycle lemma. Negative entries can be arbitrarily large in magnitude, and zero entries are allowed. Addario-Berry's proposition 2.2.1 gives an equivalent form with increments at least

- 1

and negative total; reversing the sequence and changing all signs gives the form here. ^[ref]

Four starts, two successes. For

a = (1, 1, 1, - 1)

, the sum is

k = 2

. Starts

0

and

1

give partial sums

(1, 2, 3, 2)

and

(1, 2, 1, 2)

, respectively. Start

2

gives

(1, 0, 1, 2)

and touches zero; start

3

gives

(- 1, 0, 1, 2)

and begins below zero. Thus exactly two starts are good. The rotated sequence

(- 1, 1, 1, 1)

has the same positive total, but its first start is bad: a positive final lead alone does not control earlier partial sums.

Figure 1.
All four starts of $(1, 1, 1, - 1)$ : the cycle lemma with increments at most one counts precisely the two paths whose nonempty partial sums stay strictly above zero
. **Details**.

Positions can give identical words. The sequence

(1, 1, - 1, 1, 1, - 1)

repeats a block of length three and has sum two. Its good starts are

0

and

3

, both giving the same word

(1, 1, - 1, 1, 1, - 1)

with partial sums

(1, 2, 1, 2, 3, 2)

. Starts

1

and

4

touch zero; starts

2

and

5

begin negatively. The cycle lemma with increments at most one counts two starting positions even though there is only one distinct good rotated word. Counting distinct words would lose the multiplicity that makes the statement true.

Figure 2.
Six starting positions of the repeating sequence $(1, 1, - 1, 1, 1, - 1)$ : starts $0$ and $3$ produce identical good words and count twice
. **Details**.

The upper bound matters. The one-entry sequence

(2)

has positive integer sum two, but only one starting position. Thus the sum-

k

conclusion fails for arbitrary positive increments when

k > 1

. The sum-one cycle lemma above needs no such upper bound. Strict positivity also matters: counting paths that merely stay at or above zero would include additional starts in both diagrams.

From rotation to enumeration. For a fixed admissible sequence, a start chosen from a uniform distribution on a finite set of its

n

positions is good with probability

k / n

. More generally, let

F

be any finite set of length-

n

sequences satisfying the increment bound and total

k

, closed under rotation. Double counting pairs consisting of a sequence and a good starting position gives

# {a \in F : all nonempty partial sums of a are positive} = \frac{k}{n} ∣ F ∣.

For each good output sequence and each of the

n

positions, inverse rotation gives one such pair, even when several rotated words coincide. For example, the four sequences containing three

+ 1

votes and one

- 1

vote have exactly

\frac{2}{4} (3 4) = 2

vote orders with a strictly positive running lead:

(1, 1, 1, - 1)

and

(1, 1, - 1, 1)

. This is how the cycle lemma with increments at most one converts many prefix inequalities into a simple counting factor.

Cyclic digit run

A cyclic digit run is a consecutive segment of a digit string whose successive digits all increase by one or all decrease by one modulo the base. For example,

8, 9, 0, 1

is an increasing decimal run. This refers to cyclic digit values, not to joining the final position of the string back to its first position. Overlapping run constraints can be counted with the inclusion-exclusion principle.

Finite geometry

Finite geometry studies geometric incidence structures having finitely many points, such as finite projective and affine spaces.

Increasing subsequence

An increasing subsequence of a finite sequence

x = (x_{1}, \dots, x_{n})

in a totally ordered set selects indices

1 \leq i_{1} < \dots < i_{m} \leq n

such that

x_{i_{1}} \leq x_{i_{2}} \leq \dots \leq x_{i_{m}} .

Here “increasing” means weakly increasing, also called nondecreasing: equal values are allowed, but indices must increase strictly. This is the convention of ^[ref]. A strictly increasing subsequence instead requires

x_{i_{1}} < \dots < x_{i_{m}}

. Always check which convention an algorithm uses, especially when values repeat.

An increasing subsequence may skip positions; it neither rearranges values nor requires consecutive positions. Consider the deliberately constructed example

x = (4, 1, 3, 2, 2, 5, 0) .

The indices

(2, 4, 5, 6)

select

(1, 2, 2, 5)

, an increasing subsequence of length four. The indices

(2, 3, 6)

select

(1, 3, 5)

, a strictly increasing subsequence of length three. In contrast,

(0, 1, 2, 2, 3, 4, 5)

rearranges the input and is not a subsequence. The longest consecutive nondecreasing block is

(2, 2, 5)

, of length three; requiring consecutive positions would therefore solve a different problem.

Think of an increasing subsequence as preserving ordered observations while skipping interruptions. For the example, discarding

4, 3, 0

leaves four observations with no downward step. The longest increasing subsequence asks how much of the original order can be kept. This is an order comparison, rather than a claim about the size of upward or downward changes: replacing all values by their squares when the values are nonnegative leaves every allowed selection unchanged. More generally, any strictly order-preserving relabeling has this property.

Longest increasing subsequence ( $L (x)$ )

A longest increasing subsequence is an increasing subsequence of maximum length. Write that length as

L (x)

, with

L (()) = 0

for the empty sequence; a nonempty input has

1 \leq L (x) \leq n

. Several selections can attain the same maximum. Here

L

uses the weak convention

\leq

; write

L_{<} (x)

for the maximum length of a strictly increasing subsequence. For

(2, 2, 2)

, these lengths are three and one respectively; for an input with distinct values they agree.

For

x = (4, 1, 3, 2, 2, 5, 0)

, the answer is

L (x) = 4

, attained at indices

(2, 4, 5, 6)

, while

L_{<} (x) = 3

. One useful interpretation is the smallest number of deletions needed to make the surviving sequence nondecreasing:

minimum deletions = n - L (x) .

Indeed, keeping a longest increasing subsequence attains this bound, and any valid remaining sequence is an increasing subsequence, so cannot have more than

L (x)

terms. In this example the answer is

7 - 4 = 3

. This makes

L (x)

a measure of how much order can be recovered without moving any observation.

A table that ends at each position. Let

d_{i}

be the maximum length of an increasing subsequence ending specifically at position

i

. The dynamic programming recurrence relation is

d_{i} = 1 + max ({0} \cup {d_{j} : 1 \leq j < i, x_{j} \leq x_{i}}), L (x) = max_{1 \leq i \leq n} d_{i} (n > 0) .

The zero covers a selection consisting only of

x_{i}

. Otherwise its penultimate index is an eligible

j

; append

x_{i}

to an optimal selection ending there. Fill entries in increasing index order. For strictly increasing subsequences, change the comparison to

x_{j} < x_{i}

. The strict version and reconstruction are developed in University of Toronto, CSC373 tutorial 4 solutions (2018), exercise 2; the weak version follows by allowing equality at the append step.

In the worked input, the weak table is

(1, 1, 2, 2, 3, 4, 1)

and the strict table is

(1, 1, 2, 2, 2, 3, 1)

. At the second

2

, equality extends the first

2

in the weak table. The final entry is only one, although the optimum is four: the best increasing subsequence need not finish at the last input position. Record a maximizing predecessor

p_{i} = j

whenever

d_{i} > 1

. Following these stored indices from any position maximizing

d_{i}

, then reversing them, gives an actual longest increasing subsequence. For the weak example the backward chain is

6, 5, 4, 2

Figure 1.
Skipping positions and allowing equal values changes the optimum
. An original toy input, not measured data. The colored selection keeps indices $2, 4, 5, 6$ and values $1, 2, 2, 5$ . The two dynamic programming rows give the best lengths ending at every position; the backward arrows reconstruct the weak longest increasing subsequence. **Details**.

Scanning all earlier positions for each

i

uses time complexity

O (n^{2})

and space complexity

O (n)

for lengths and predecessors, using Big O notation and assuming constant-time comparisons and operations on indices.

Keep the easiest ending to extend. The faster algorithm maintains a minimum-tail table for increasing subsequences:

T_{ℓ}

is the smallest final value of any length-

ℓ

increasing subsequence in the processed prefix. For equal lengths, a smaller ending permits every future extension allowed by a larger ending. Thus only one best ending per length is needed. The table is nondecreasing, since removing the last term of a length-

(ℓ + 1)

selection gives

T_{ℓ} \leq T_{ℓ + 1}

. Start with an empty table. On reading

v = x_{i}

, use binary search to find the first entry strictly greater than

v

: replace it by

v

, or append

v

if there is no such entry. Its position is one beyond the longest existing length whose ending is at most

v

. See Liben-Nowell, Vee and Zhu, section 3.1 and Figure 1.

Duplicates determine the binary search rule: weak increase replaces the first

T_{ℓ} > v

, whereas strict increase replaces the first

T_{ℓ} \geq v

. In Python these positions are returned by bisect_right(T, v) and bisect_left(T, v) respectively, counting positions from zero. Replace an entry or append; do not insert and shift the remaining entries. The documented equality rules are in Python documentation, bisect_left and bisect_right. Each search takes

O (lo g (n + 1))

comparisons, giving time complexity

O (n lo g (n + 1))

, conventionally

O (n lo g n)

for

n \geq 2

, and space complexity

O (L (x))

for the weak length alone.

Figure 2.
Two binary-search tie rules give different minimum-tail tables
. Original exact traces for the same toy input, not measured data. Each cell shows a tail value and the input index supplying it; the outlined cell was updated in that row. At the second $2$ , the weak algorithm appends and the strict algorithm replaces. The final weak table has length four, but its supplier indices $7, 4, 5, 6$ are not in increasing order. **Details**.

A length certificate needs separate reconstruction. The final weak tail values are

(0, 2, 2, 5)

, but they do not form an increasing subsequence of this input: the zero occurs last. Each table entry certifies a selection of its own length; the entries need not come from one compatible selection. To recover a longest increasing subsequence during the fast algorithm, store a supplier index

q_{ℓ}

for each tail and a predecessor index for each input position. Before replacing slot

r

, save

p_{i} = q_{r - 1}

, or no predecessor if

r = 1

, then set

q_{r} = i

. Later replacements leave saved

p_{i}

unchanged. Follow predecessors from the final

q_{L (x)}

and reverse. This uses space complexity

O (n)

and returns indices

(2, 4, 5, 6)

for the weak trace. The same construction works with the strict comparator; compare the two auxiliary arrays in CP Algorithms contributors, restoring the subsequence after binary search.

Deleting or changing one term. If

x^{∖ k}

deletes position

k

, then

L (x) - 1 \leq L (x^{∖ k}) \leq L (x) .

(3)

Deleting cannot create a longer increasing subsequence; removing position

k

from a previously optimal selection loses at most one term. If

x^{'}

instead changes just the value at position

k

, both inputs have the same deleted sequence, so their lengths each lie between its length and its length plus one. Consequently

∣ L (x^{'}) - L (x) ∣ \leq 1

. These bounds also hold for strictly increasing subsequences. In the weak example, deleting either

2

lowers the length to three, while deleting the final zero leaves it four. This is a Lipschitz bound for single-term edits, regardless of the numerical size of a replacement. Insertion has the same bound by reversing deletion, so

m

insertions, deletions or replacements can change

L

by at most

m

For historical context, ^[ref] studies the comparison count for distinct elements of a totally ordered set. Its distinctness assumption makes the weak and strict conventions coincide. No distinctness assumption is needed for the comparator-specific algorithms above.

Minimum-tail table for increasing subsequences ( $T_{ℓ}$ )

For a processed prefix

(x_{1}, \dots, x_{i})

, the minimum-tail table for increasing subsequences stores

T_{ℓ} = min {x_{j_{ℓ}} : 1 \leq j_{1} < \dots < j_{ℓ} \leq i, x_{j_{1}} \leq \dots \leq x_{j_{ℓ}}}, 1 \leq ℓ \leq L (x_{1}, \dots, x_{i}) .

There is no slot for an unattainable length. The table records minimum endings, rather than the terms of one longest increasing subsequence. Replacing the value comparisons by

<

gives the corresponding table for strictly increasing subsequences, whose entries are strictly increasing.

First row of RSK as a minimum-tail table

For a permutation input, the first row of its RSK insertion tableau is the minimum-tail table for increasing subsequences: its

j

th entry is the least attainable final value of a strictly increasing subsequence of length

j

in the processed prefix. Inserting

z

replaces the first entry larger than

z

, or appends if none exists. In replacement position

r

, the previous entry in position

r - 1

supplies a subsequence that can be extended by

z

. Shorter minimum tails were already smaller, and a longer subsequence ending at

z

would require an old tail in position at least

r

smaller than

z

, contrary to the replacement rule. This proves the invariant inductively. Consequently the first-row length is the longest increasing subsequence length. The row entries need not be a subsequence together: input

2, 4, 3, 1

gives first row

1, 3

, although one occurs after three. They are minima for different lengths, obtained from potentially different subsequences.

Strictly increasing subsequence

A strictly increasing subsequence selects indices

i_{1} < \dots < i_{m}

of a sequence with

x_{i_{1}} < \dots < x_{i_{m}}

. Equal values cannot both occur in it. Its maximum possible length is

L_{<} (x)

, with

L_{<} (()) = 0

; in general

L_{<} (x) \leq L (x)

for the weak longest increasing subsequence. Use strict comparisons in the dynamic programming recurrence relation and replace the first tail at least as large as the next value in the binary search algorithm.

Additive combinatorics

Additive combinatorics studies how the cardinalities and sumset representation functions of sumsets reveal structure in finite sets contained in abelian groups. Write the group operation as addition: the ambient abelian group may be the integers

Z

, a finite cyclic group, or another abelian group. The same definitions apply, but the ambient group changes which bounds are possible.

The basic experiment is to add every ordered pair of members of a finite set. The sumset records the distinct answers; the sumset representation function records how often each answer occurs; the additive energy counts coincidences between those answers. An arithmetic progression produces many repeated sums, so its sumset grows slowly and its additive energy is relatively large. The doubling constant measures that growth relative to the original cardinality.

The examples below compare the arithmetic progression

A = {0, 1, 2, 3}

with the more spread-out integer set

B = {0, 1, 4, 10}

. Their four members give sixteen ordered pairs in each case, but different numbers of distinct sums. This small comparison illustrates the definitions; it does not establish a claim about arbitrarily large sets. For a systematic introduction, see Tao and Vu's author page for Additive Combinatorics, with free sample chapters on sum set estimates and additive geometry.

Furstenberg-Katznelson theorem ( $a + tF \subseteq A$ )

The multidimensional Szemerédi theorem says that a subset

A \subseteq Z^{d}

with positive upper density contains a translated positive integer dilate

a + tF

of every finite set

F \subseteq Z^{d}

. In the finite formulation, for every

α > 0

and finite

F

, all sufficiently large integer boxes have this property for every subset occupying at least an

α

fraction of the box. The one-dimensional case for

F = {0, 1, \dots, r - 1}

is the Szemerédi theorem. The general result follows from multiple recurrence for commuting measure-preserving transformations.

Bracket-linear frequency function ( $θ (h) = β {γh} (mod 1)$ )

A frequency function built from an affine variable and its fractional part. Irrational

γ

and

β

can give many exact additive relations because each pair sum has only two possible floor carries. For example

β = 3

γ = 2

gives

≫ N^{3}

additive quadruples on

[- N, N]

, but agreement with every ordinary affine function occurs on only

o (N)

shifts. Integer floor points underlying affine agreement must be collinear.

Four-term progression hypergraph encoding ( $L_{i} = \sum_{j \neq = i} (j - i) x_{j}$ )

Use four parts indexed by

0, 1, 2, 3

in a cyclic group

G

, and include the triple missing part

i

when

L_{i} \in A

. A transversal three-uniform tetrahedron then has the four values

S_{1} - i S_{0}

, where

S_{0} = \sum_{j} x_{j}

and

S_{1} = \sum_{j} j x_{j}

, so it encodes a four-term arithmetic progression. Constant progressions give

∣ A ∣∣ G ∣^{2}

edge-disjoint tetrahedra. This is the bridge from the tetrahedron removal lemma to the Szemerédi theorem.

Roth theorem on three-term arithmetic progressions

For every

δ > 0

, every sufficiently long integer interval has a nonconstant three-term arithmetic progression in each subset of subset density at least

δ

. This is a theorem about additive combinatorics, distinct from the Roth theorem on approximation of algebraic irrational numbers. The Roth density-increment step proves it by repeatedly increasing subset density on a shorter arithmetic progression.

Roth density increment on an integer progression ( $∣ P ∣ \geq c δ^{2} N, δ_{P} \geq δ + c δ^{2}$ )

If a density-

δ

subset of a sufficiently long integer interval has no nonconstant three-term arithmetic progression, Fourier expansion of the progression count gives a large coefficient of its balanced indicator. Dirichlet approximation supplies a step at most

N

on which that character varies slowly. Partitioning the interval into equal-length progressions of that step, and controlling the short tails, produces the displayed density increment. Iteration must terminate since density cannot exceed one. The same argument treats the three-point pattern with coefficients

2, - 3, 1

Triangle-removal proof of Roth theorem

Embed

A \subseteq [N]

in the odd cyclic group

G = Z / (2 N + 1) Z

, so additive three-term relations in

A

cannot wrap around. Form three copies of

G

, putting edges

x \sim y

when

y - x \in A

y \sim z

when

z - y \in A

, and

x \sim z

when

(z - x) /2 \in A

. A triangle in a graph encodes

a + b = 2 c

A

. If

A

has no nonconstant arithmetic progression, every triangle in a graph has

a = b = c

; there are exactly

∣ G ∣∣ A ∣

triangles in a graph, and they are edge-disjoint. Thus at least

∣ G ∣∣ A ∣

edges must be removed to eliminate them. For fixed positive subset density of

A

, this is a positive fraction of the squared vertex count, whereas the triangle in a graph count is only quadratic. The triangle removal lemma permits deletion of an arbitrarily small quadratic fraction when the cubic triangle in a graph subset density is sufficiently small. This contradiction establishes Roth theorem on three-term arithmetic progressions.

Classical Roth bound for three-term progressions ( $r_{3} (N) ≪ N / lo g lo g N$ )

Write

r_{3} (N)

for the maximum cardinality of a subset of

[N]

containing no nonconstant three-term arithmetic progression. There is an absolute constant

C

such that every three-term-progression-free subset

A \subseteq [N]

satisfies

∣ A ∣ \leq CN / lo g lo g N

for

N \geq 3

. A quantitative Roth density-increment step gives, for subset density

δ

and

N \geq 4 \cdot 1 0^{6} δ^{- 4}

, a arithmetic progression of length at least

δ^{2} N /2000

and increased subset density at least

δ + δ^{2} /64

. The increment decreases reciprocal subset density by at least

1/65

, so fewer than

⌈ 65/ δ ⌉

iterations are possible. If

N_{j}

is the successive length, then

lo g N_{j + 1} \geq \frac{1}{2} lo g N_{j} - lo g (2000/ δ^{2})

, using the initial subset density to bound all later ones. Hence

lo g N_{j} \geq 2^{- j} lo g N - 2 lo g (2000/ δ^{2})

. If

δ lo g lo g N

exceeds a sufficiently large absolute constant, all these intervals remain above the density increment threshold, a contradiction. This proves the displayed bound. The result is a classical quantitative version of Roth theorem on three-term arithmetic progressions, without asserting an optimal bound.

High-energy Roth theorem

For fixed

θ > 0

, a sufficiently large finite set of integers with additive energy at least

θ ∣ A ∣^{3}

has a nonconstant three-term arithmetic progression. The Balog-Szemerédi-Gowers theorem and Ruzsa modelling lemma reduce the problem to the Roth theorem on three-term arithmetic progressions in a dense cyclic model.

Product set ( $A \cdot B$ )

The product set of two sets of real numbers is

A \cdot B = {ab : a \in A, b \in B}

. It is a multiplicative counterpart of a sumset, not the Cartesian product

A \times B

Multiplicative energy ( $E (A, B)$ )

For finite sets of nonzero real numbers, the multiplicative energy is the number of quadruples

(a, b, c, d) \in A \times B \times A \times B

satisfying

a / b = c / d

. Swapping

b, d

shows that it also counts quadruples with

ab = c d

. Thus

E (A, B) = \sum_{x} r_{A \cdot B} (x)^{2}

, where

r_{A \cdot B} (x)

counts product representations. The Cauchy-Schwarz inequality yields

E (A, B) \geq ∣ A ∣^{2} ∣ B ∣^{2} /∣ A \cdot B ∣

Multiplicative energy sumset bound ( $E (A, B) \leq 4 ⌈ lo g ∣ B ∣ ⌉ ∣ A + A ∣∣ B + B ∣$ )

For finite sets of positive real numbers

A, B

with

∣ B ∣ \geq 2

E (A, B) \leq 4 ⌈ lo g ∣ B ∣ ⌉ ∣ A + A ∣∣ B + B ∣

, with natural or binary logarithm. Partition ray occupancies of

A \times B

into

⌈ lo g ∣ B ∣ ⌉

classes of multiplicative width

e

, or width

2

for the binary convention. Injectivity of sums on two distinct rays and disjoint open planar sectors bound each class's sum of squared occupancies by

4∣ A + A ∣∣ B + B ∣

. A singleton class contributes at most

∣ A ∣∣ B ∣

. Combining this with the energy lower bound gives a sum-product inequality.

Corner in an integer grid ( ${(x, y), (x, y + d), (x + d, y)}, d \neq = 0$ )

A corner consists of these three points in the integer grid, all contained in the set being studied. The displacement may be positive or negative, but must be nonzero, so the points are distinct. The corners theorem guarantees a corner in every subset of positive fixed density of a finite subset of a sufficiently large square grid.

Corners theorem

For every

δ > 0

, all sufficiently large integers

n

have the property that every

A \subseteq [n]^{2}

with

∣ A ∣ \geq δ n^{2}

contains a corner in an integer grid. The tripartite graph encoding of a grid turns the absence of a corner into a family of many edge-disjoint triangles but only quadratically many total triangles in a graph, contradicting the triangle removal lemma.

Cut norm ( $∥ H ∥_{cut} = max_{A, B} ∣ E H 1_{A} 1_{B} ∣$ )

For a real-valued function

H

on a nonempty finite Cartesian product

X \times Y

, its normalized cut norm is the maximum of

∣ E_{x, y} H (x, y) 1_{A} (x) 1_{B} (y) ∣

over

A \subseteq X, B \subseteq Y

. It measures all rectangular subset discrepancies. The convention using arbitrary test functions bounded by one is equivalent within a factor of four, by decomposing their positive and negative parts into indicator functions.

Non-abelian additive combinatorics

Non-abelian additive combinatorics studies product sets and configuration counts in noncommutative groups. Fourier analysis on a finite group and quasirandom groups connect small-dimensional group representations with multiplicative mixing.

Matrix-valued Gowers U2 quantity ( $∥ f ∥_{U^{2}}^{4} = E_{x y^{- 1} z w^{- 1} = e} tr (f (x) f (y)^{} f (z) f (w)^{})$ )