Extremal Combinatorics

← Back to Domain-Specific Abstractions by Domain

3 domain-specific abstractions whose origin domain is Extremal Combinatorics.

• Erdős–Ko–Rado Theorem — For n at least 2k, a pairwise-intersecting family of k-subsets of an n-element set has at most C(n-1,k-1) members, attained by every full star.
• Flag algebra — Razborov's algebraic framework for asymptotic densities of partially labeled finite structures, turning extremal combinatorics inequalities into positive semidefinite and semidefinite-programming certificates.
• Turán number — The minimum number of r-element blocks on n vertices needed so every k-element vertex subset contains at least one block.