41 articles
Sauer–Shelah lemma
The Sauer–Shelah lemma, also called the Perles–Sauer–Shelah lemma, is a combinatorics theorem bounding a set family's size by its VC dimension, with applications in machine learning.
Set cover problem
The set cover problem, or set covering, is a combinatorial optimization problem asking for the smallest collection of sets whose union covers every element; it was one of Karp's original 21 NP-complete problems.
Sidon sequence
A Sidon sequence, also called a B₂-sequence or Sidon set, is a sequence of integers in which all pairwise sums are distinct, introduced by Simon Sidon in 1932.
Sperner property of partially ordered sets
The Sperner property of partially ordered sets, or Sperner posets, holds when no antichain is larger than the largest rank level; Sperner proved it for subset lattices in 1928.
Subset sum problem
The subset sum problem asks whether some subset of a set of integers sums exactly to a target. It was proved NP-complete in Richard Karp's 1972 paper.
Szemerédi's theorem
Szemerédi's theorem states that every set of integers with positive upper density contains arithmetic progressions of every finite length. Endre Szemerédi proved it in 1975.
Turán number
The Turán number ex(n, F) is the maximum number of edges in an n-vertex graph or hypergraph containing no copy of F, central to extremal graph theory.
Union-closed sets conjecture
The union-closed sets conjecture, also known as Frankl's conjecture, is an open problem stating that every finite union-closed family of sets has an element in at least half its members.
Van der Waerden's theorem
Van der Waerden's theorem, a Ramsey theory result conjectured by Baudet and proved in 1927, states that any coloring of a long enough interval of integers contains a monochromatic arithmetic progression.
VC dimension
The Vapnik–Chervonenkis (VC) dimension is a measure of the complexity of a family of sets: the largest number of points on which the family realizes every possible labeling.
Zarankiewicz problem
The Zarankiewicz problem asks for the maximum number of edges in a bipartite graph with given part sizes that contains no complete bipartite subgraph K(s,t), and is central to extremal graph theory.