56 articles
Lyndon word
A Lyndon word is a finite word over an ordered alphabet that is lexicographically smaller than all of its nontrivial rotations, introduced by Roger Lyndon in 1954.
MacMahon partition analysis
MacMahon partition analysis is a combinatorial method introduced by Percy MacMahon in 1915 that counts solutions of linear Diophantine inequalities via the Omega operator, revived by George Andrews in the late 1990s.
Mahonian statistic
A Mahonian statistic is a statistic on permutations whose distribution equals that of the inversion number; the major index is the other prototype, both named for Percy MacMahon.
Matching polynomial
The matching polynomial of a graph is a polynomial whose coefficients count the graph's matchings by size, introduced by Farrell in 1979 and studied by Heilmann and Lieb.
Matroid
A matroid, also called a combinatorial pregeometry, is a combinatorial structure abstracting linear independence in vector spaces and cycle-freedom in graphs, introduced by Hassler Whitney in 1935.
Modular lattice
A modular lattice is a lattice satisfying the modular law, a weakening of distributivity formulated by Richard Dedekind around 1900; examples include subspaces of a vector space and normal subgroups of a group.
Moore graph
A Moore graph is a regular graph of given degree and diameter containing the maximum possible number of vertices, attaining the Moore bound; examples include the Petersen graph.
Newton's identities
Newton's identities, also called the Newton–Girard identities, are relations expressing the power sums of variables in terms of elementary symmetric polynomials, first published by Newton in 1707.
Order theory
Order theory is the branch of mathematics that studies partially ordered sets, or posets, together with structures built on them such as lattices and ordered algebraic systems.
Parity bit
A parity bit, also called a check bit, is an extra binary digit appended to data so the count of 1s is even or odd, detecting single-bit errors.
Parking function
A parking function is a sequence of positive integers where cars with those preferences can all park in a line of spots, named by Konheim and Weiss in 1966.
Plethysm
Plethysm is an operation on symmetric functions, written f[g], in which one symmetric function is substituted into another, introduced by D. E. Littlewood in 1936.
Reed–Muller code
Reed–Muller codes are a family of linear error-correcting codes whose codewords are evaluations of multivariate polynomials over finite fields, introduced in 1954 by David E. Muller.
Reed–Solomon error correction
Reed–Solomon error correction is a family of error-correcting codes, introduced by Irving Reed and Gustave Solomon in 1960, used in QR codes, CDs, and spacecraft.
Residuated lattice
A residuated lattice is an algebraic structure combining a lattice with a monoid whose multiplication admits residuals, introduced by Ward and Dilworth in the late 1930s.
Robinson–Schensted correspondence
The Robinson–Schensted correspondence, also called the Robinson–Schensted algorithm, is a bijection in combinatorics that assigns to each permutation a pair of standard Young tableaux of the same shape.
Sheffer sequence
A Sheffer sequence, also called a Sheffer polynomial or poweroid, is a polynomial sequence in umbral calculus that includes the Hermite, Laguerre, and Charlier polynomials.
Simplicial complex
A simplicial complex, also called a geometric simplicial complex, is a combinatorial structure of vertices and simplices used to encode topological spaces as finite data.
Singleton bound
The Singleton bound is an upper limit on the minimum distance of an error-correcting code: a code of length n, dimension k, and distance d satisfies d ≤ n − k + 1.
Specht module
A Specht module is a module for the symmetric group built from Young tableaux of a given partition shape, introduced by Wilhelm Specht in 1935.
Strongly regular graph
A strongly regular graph is a regular graph in which adjacent and non-adjacent vertex pairs have constant numbers of common neighbors, described by parameters (n, k, λ, μ).
Symmetric function
A symmetric function is a function of several variables whose value does not change under any permutation of its variables; most often it means a symmetric polynomial in n variables.
Tamari lattice
The Tamari lattice is a partially ordered set whose elements are binary bracketings of a fixed number of symbols, ordered by applying the associativity rule; Dov Tamari introduced it in his 1951 thesis.
Tutte polynomial
The Tutte polynomial, named for mathematician and codebreaker W. T. Tutte, is a two-variable invariant of graphs and matroids whose evaluations count spanning trees, acyclic orientations, and proper colorings.
Umbral calculus
Umbral calculus, also known as Blissard's symbolic method, is an algebraic technique treating a sequence's index as an exponent, made rigorous by Gian-Carlo Rota in the 1970s.
Young symmetrizer
A Young symmetrizer is an element of the symmetric group algebra that symmetrizes over a Young tableau's rows and antisymmetrizes over its columns, constructing every irreducible representation.