Extremal Combinatorics — Dilworth, Erdős-Ko-Rado & Sperner

June 2026 · 28 min read

What Is Extremal Combinatorics?

Extremal combinatorics asks one deceptively simple question: how large (or small) can a combinatorial structure be while satisfying a given property? The answers are some of the most elegant results in mathematics — and they appear constantly in competitive programming, often hiding behind seemingly unrelated problem statements.

Consider a few motivating questions:

• What is the maximum number of edges a graph on n vertices can have without containing a triangle?
• Given a poset, what is the minimum number of chains needed to partition every element?
• How large can a family of subsets of {1, …, n} be if no set contains another?
• How many k-element subsets of {1, …, n} can you choose so that every pair intersects?

Each of these has a sharp, beautiful answer — and each answer has algorithmic consequences. In CP, extremal results serve two purposes: they give you tight bounds on the answer to a counting or optimisation problem, and they suggest constructions that achieve those bounds.

This post covers four cornerstones of the field — Sperner's theorem, Dilworth's theorem, the Erdős-Ko-Rado theorem, and Turán's theorem — each with proofs, C++ implementations, and competitive-programming applications.

Sperner's Theorem

Setup

Let [n] = {1, 2, …, n}. The power set 2^[n] is the set of all subsets of [n], ordered by inclusion: A ≤ B iff A ⊆ B. A family ℱ ⊆ 2^[n] is an antichain if no member of ℱ is a subset of another.

For n = 4 the largest antichain has C(4, 2) = 6 elements — for instance, all 2-element subsets: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}. No one of these contains another, and you cannot do better.

The LYM Inequality

The cleanest proof uses the Lubell–Yamamoto–Meshalkin (LYM) inequality, which is itself a fundamental tool in extremal set theory.

Proof. Count the number of maximal chains in 2^[n] (chains of length n+1 from ∅ to [n]). There are exactly n! such chains, because building one amounts to choosing a permutation of [n] and adding elements one at a time.

Each set A with |A| = k lies on exactly k! · (n−k)! maximal chains: choose any order for the k elements inside A (k! ways) and any order for the n−k elements outside (giving (n−k)! ways). Since ℱ is an antichain, no maximal chain passes through two members of ℱ. Hence:

Σ_{A ∈ ℱ} k! · (n−k)! ≤ n!

Dividing both sides by n! gives the LYM inequality. Now, since 1/C(n,k) ≤ 1/C(n, ⌊n/2⌋) for all k, the inequality implies m / C(n, ⌊n/2⌋) ≤ 1, hence m ≤ C(n, ⌊n/2⌋). ■

Sperner via Dilworth

An alternative proof proceeds through Dilworth's theorem (below). Partition 2^[n] into C(n, ⌊n/2⌋) symmetric chains — chains that start at level k and end at level n−k. Since every antichain picks at most one element per chain, the bound follows. This symmetric chain decomposition is constructive and gives an explicit optimal antichain.

Dilworth's Theorem

Posets, Chains, and Antichains

A partially ordered set (poset) (P, ≤) is a set P with a reflexive, antisymmetric, transitive relation. A chain is a totally ordered subset; an antichain is a set of pairwise incomparable elements. A chain partition of P is a collection of disjoint chains whose union is P.

One direction is easy: if the largest antichain has size w, then every chain partition needs at least w chains (because the w elements of the antichain must go to different chains). The hard part is constructing a chain partition of exactly w chains.

Proof Sketch

The standard proof is by strong induction on |P|. Let w be the width (max antichain size). If every maximal chain C satisfies w(P \ C) = w − 1, we can induct. Otherwise, there exists a maximal antichain A of size w that does not include the maximum or minimum element of any maximal chain. Let D = {x : x ≤ a for some a ∈ A} and U = {x : x ≥ a for some a ∈ A}. Then D ∪ U = P (since A is maximal), D ∩ U = A, and both D and U have width w. By induction, D and U each have w-chain partitions; gluing them along A yields a w-chain partition of P. ■

Connection to König's Theorem

Dilworth's theorem is the poset analogue of König's theorem in bipartite graphs. In fact, the minimum chain partition can be computed by modelling the poset as a bipartite graph and running maximum matching:

• Create nodes u_x and v_x for each element x ∈ P.
• Add edge (u_x, v_y) whenever x < y in the poset.
• A maximum matching of size m yields a chain partition of |P| − m chains.

Conversely, the width w = |P| − m, and by König's theorem the minimum vertex cover (= m) equals the maximum matching, confirming Dilworth.

The LIS Connection

Consider the poset of an integer sequence a₁, …, a_n where i ≤ j iff i < j and a_i ≤ a_j. A chain is a longest increasing subsequence (LIS), and an antichain is a longest non-increasing subsequence. By Dilworth's theorem:

minimum number of non-increasing subsequences to partition = LIS length

Equivalently, by the Erdős–Szekeres theorem, any sequence of length > r · s contains an increasing subsequence of length r+1 or a non-increasing subsequence of length s+1.

Erdős-Ko-Rado Theorem

Intersecting Families

A family ℱ of k-element subsets of [n] is called intersecting if every pair of sets in ℱ shares at least one element: A ∩ B ≠ ∅ for all A, B ∈ ℱ.

The simplest intersecting family is the star (or sunflower kernel): fix an element x ∈ [n] and take all k-subsets containing x. This gives C(n−1, k−1) sets.

Katona's Proof (Cyclic Permutation Trick)

Katona's 1972 proof is one of the most beautiful short proofs in combinatorics. It avoids induction entirely and uses a clever counting argument with cyclic permutations.

Setup. Arrange the elements 1, 2, …, n around a circle in some order σ. An arc of length k is a set of k consecutive elements on the circle. There are exactly n arcs of length k on a circle of n elements.

Key claim: At most k of these n arcs can belong to an intersecting family ℱ. To see this, note that if an arc A is in ℱ, then the "antipodal" arc (shifted by k positions) is disjoint from A (since n ≥ 2k), hence not in ℱ. More carefully, among any k consecutive arcs in the cyclic order, at most k can be pairwise intersecting, and one can show at most k arcs from ℱ appear.

Counting. Sum over all n! cyclic permutations σ. Each set S ∈ ℱ appears as an arc in exactly k! · (n−k)! permutations (order the k elements of S consecutively, then order the remaining n−k). By the claim, for each σ at most k arcs from ℱ appear. Hence:

|ℱ| · k! · (n−k)! ≤ k · n!

Dividing by k! · (n−k)! gives |ℱ| ≤ k · n! / (k! · (n−k)!) = k · C(n,k) / n = C(n−1, k−1). ■

Worked Example

Let n = 5, k = 2. Then C(4, 1) = 4. Indeed, fix element 1: the star is {1,2}, {1,3}, {1,4}, {1,5} — four pairs, and any two share element 1. You cannot have 5 pairwise-intersecting pairs from [5], because {2,3} and {4,5} don't intersect.

Turán's Theorem

The Extremal Graph Problem

The oldest and most fundamental question in extremal graph theory: what is the maximum number of edges in a graph on n vertices that contains no complete subgraph K_r? This maximum is denoted ex(n, K_r).

The Turán Graph T(n, p)

T(n, p) is the complete p-partite graph where the n vertices are divided into p parts as equally as possible. If n = q·p + s with 0 ≤ s < p, then s parts have size q+1 and p−s parts have size q. Two vertices are adjacent iff they belong to different parts.

The exact edge count of T(n, p) is:

|E(T(n,p))| = (n² − Σ_i n_i²) / 2

where n_i is the size of part i. With s parts of size q+1 and p−s parts of size q:

|E| = (n² − s(q+1)² − (p−s)q²) / 2

Why Is T(n, r−1) K_r-Free?

A clique K_r needs r vertices that are pairwise adjacent. In a (r−1)-partite graph, by pigeonhole, at least two of the r vertices must share a part — and vertices in the same part are non-adjacent. Hence no K_r exists.

C++ Implementations

Turán Number Computation

Given n and r, compute the exact number of edges in the Turán graph T(n, r−1). This is useful when a problem asks "maximum edges with no K_r."

#include <bits/stdc++.h>
using namespace std;

long long turan_edges(long long n, int r) {
    // T(n, r-1): complete (r-1)-partite graph, balanced parts
    int p = r - 1;
    long long q = n / p, s = n % p;
    // s parts of size (q+1), (p-s) parts of size q
    long long sum_sq = s * (q + 1) * (q + 1) + (p - s) * q * q;
    return (n * n - sum_sq) / 2;
}

int main() {
    int n, r;
    cin >> n >> r;
    cout << turan_edges(n, r) << "\n";
    // Example: n=6, r=3 → T(6,2) = K_{3,3} → 9 edges
    return 0;
}

LIS via Patience Sorting (Dilworth Application)

The Longest Increasing Subsequence is the classic algorithmic manifestation of Dilworth's theorem. In the dominance poset of a sequence, a chain is an increasing subsequence and an antichain is a non-increasing subsequence. The minimum number of non-increasing subsequences to partition the sequence equals the LIS length.

The O(n log n) patience-sorting algorithm computes the LIS length and simultaneously gives a chain decomposition (via Dilworth): each "pile" in patience sorting is a non-increasing subsequence.

int lis_length(const vector<int>& a) {
    // tails[i] = smallest tail of all increasing subsequences of length i+1
    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end())
            tails.push_back(x);
        else
            *it = x;
    }
    return (int)tails.size();
}

// Full LIS recovery with predecessor tracking
vector<int> lis_full(const vector<int>& a) {
    int n = a.size();
    vector<int> tails, tail_idx, pred(n, -1);
    vector<int> pos; // pos[i] = index in a[] of tails[i]

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tails.begin(), tails.end(), a[i]);
        int j = it - tails.begin();
        if (it == tails.end()) {
            tails.push_back(a[i]);
            pos.push_back(i);
        } else {
            *it = a[i];
            pos[j] = i;
        }
        pred[i] = (j > 0) ? pos[j - 1] : -1;
    }

    // Reconstruct
    vector<int> result;
    for (int i = pos.back(); i != -1; i = pred[i])
        result.push_back(a[i]);
    reverse(result.begin(), result.end());
    return result;
}

Checking a Sperner Family & Computing Max Antichain Size

Given a collection of subsets (encoded as bitmasks), verify that it forms an antichain and compute the maximum antichain size C(n, ⌊n/2⌋).

bool is_antichain(const vector<int>& family) {
    int m = family.size();
    for (int i = 0; i < m; i++)
        for (int j = i + 1; j < m; j++)
            if ((family[i] & family[j]) == family[i] ||
                (family[i] & family[j]) == family[j])
                return false;  // one is subset of the other
    return true;
}

long long sperner_max(int n) {
    // C(n, floor(n/2))
    long long result = 1;
    int k = n / 2;
    for (int i = 0; i < k; i++)
        result = result * (n - i) / (i + 1);
    return result;
}

// Verify LYM inequality for a family given as subset sizes
bool check_lym(int n, const vector<int>& sizes) {
    // sizes[i] = |A_i| for each set in the antichain
    // Check: sum of 1/C(n, |A_i|) <= 1
    // Use fractions or doubles for a quick check
    double sum = 0.0;
    vector<double> binom(n + 1);
    binom[0] = 1;
    for (int i = 1; i <= n; i++)
        binom[i] = binom[i - 1] * (n - i + 1) / i;
    for (int s : sizes)
        sum += 1.0 / binom[s];
    return sum <= 1.0 + 1e-9;
}

Minimum Path Cover in DAG (Dilworth via Matching)

Dilworth's theorem reduces to bipartite matching. For a DAG on n vertices, the minimum number of vertex-disjoint paths to cover all vertices equals n minus the maximum matching in the associated bipartite graph.

struct BipartiteMatching {
    int n;
    vector<vector<int>> adj;
    vector<int> match_l, match_r;

    BipartiteMatching(int n) : n(n), adj(n), match_l(n, -1), match_r(n, -1) {}

    void add_edge(int u, int v) { adj[u].push_back(v); }

    bool dfs(int u, vector<bool>& visited) {
        for (int v : adj[u]) {
            if (visited[v]) continue;
            visited[v] = true;
            if (match_r[v] == -1 || dfs(match_r[v], visited)) {
                match_l[u] = v;
                match_r[v] = u;
                return true;
            }
        }
        return false;
    }

    int max_matching() {
        int result = 0;
        for (int u = 0; u < n; u++) {
            vector<bool> visited(n, false);
            if (dfs(u, visited)) result++;
        }
        return result;
    }
};

// Minimum path cover of DAG with n vertices and edge list
int min_path_cover(int n, const vector<pair<int,int>>& edges) {
    BipartiteMatching bm(n);
    for (auto [u, v] : edges)
        bm.add_edge(u, v);
    return n - bm.max_matching();
}

CP Applications

Dilworth ↔ Minimum Path Cover in DAG

This is the single most important algorithmic application of Dilworth's theorem in competitive programming. The problem: given a DAG, find the minimum number of vertex-disjoint paths that cover every vertex.

Model the DAG as a poset (u ≤ v iff u can reach v). A chain in this poset is a directed path. By Dilworth, the minimum chain cover equals the maximum antichain. Algorithmically, as shown above, this reduces to bipartite matching in O(V · E) time using Hopcroft-Karp or the Hungarian algorithm.

Example — Minimum Number of Pilots

Model flights as nodes. Add edge A → B whenever A finishes before B starts. This gives a DAG. The answer is the minimum path cover = n − (maximum matching). This is a direct application of Dilworth's theorem.

Sperner for Bounding Set Family Sizes

Problems that ask "how many subsets can you choose such that no subset contains another" are directly answered by Sperner's theorem: the answer is C(n, ⌊n/2⌋). Variations include weighted antichains (use the LYM inequality to bound) and antichains in product posets.

The LYM inequality is particularly useful in problems where you need to show that a family with a certain structure cannot exceed a given size. If you can prove the family is an antichain, LYM gives you the bound for free.

EKR for Intersection Constraints

Contest problems sometimes ask: "choose the maximum number of committees of size k from n people such that every pair of committees shares a member." This is the Erdős-Ko-Rado setting, and the answer is C(n−1, k−1) for n ≥ 2k.

A subtler application: if a problem gives you k-subsets and asks you to check whether a family is "maximally intersecting," verify that |ℱ| = C(n−1, k−1) and that all sets share a common element.

Turán for Graph Density Bounds

When a problem guarantees that a graph is K_r-free (or equivalently, that the chromatic number is at most r−1), Turán's theorem gives you a tight upper bound on the number of edges. This is useful for:

• Proving that a greedy algorithm terminates quickly (the graph is sparse).
• Bounding the answer in counting problems: "at most ex(n, K_r) edges."
• Constructing the densest K_r-free graph for extremal constructions.

Contest Walkthrough — Longest Increasing Subsequences

By Dilworth's theorem applied to the "dominance" poset (i < j and a[i] < a[j]), the minimum number of decreasing subsequences equals the length of the longest increasing subsequence. So simply compute LIS in O(n log n).

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    // LIS length = min number of decreasing subsequences (Dilworth)
    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << tails.size() << "\n";
    return 0;
}

Summary

Extremal combinatorics provides a powerful toolkit for competitive programming. Here are the key takeaways:

• Sperner's Theorem: maximum antichain in 2^[n] has size C(n, ⌊n/2⌋). Proved via the LYM inequality: Σ 1/C(n, |A_i|) ≤ 1.
• Dilworth's Theorem: max antichain = min chain partition. Algorithmically, this reduces to bipartite matching. The most common CP application is minimum path cover in a DAG.
• Erdős-Ko-Rado: the largest intersecting family of k-subsets of [n] (with n ≥ 2k) has size C(n−1, k−1). Katona's cyclic-permutation proof is a model of elegance.
• Turán's Theorem: ex(n, K_r) = edges in the balanced complete (r−1)-partite graph. Gives tight density bounds for K_r-free graphs.

In the next post we will explore Matroid Theory, which unifies many of the greedy-algorithm results in combinatorial optimisation and provides a framework for understanding when the greedy approach is optimal.