Tricki
a repository of mathematical know-how

Revision of Extremal combinatorics front page from Fri, 12/12/2008 - 11:17

Quick description

Extremal combinatorics concerns problems in which one is trying to maximize or minimize a parameter associated with a combinatorial structure, subject to certain constraints. For example, a classic theorem of extremal combinatorics is Turán's theorem, which determines how many edges a graph can have before it is forced to contain the complete graph K_r as a subgraph. The methods used in extremal combinatorics are extremely varied. This page starts with links to articles about these methods and continues with a short essay about how to decide which methods are appropriate for which problems.

Some important methods in extremal combinatorics

Algebraic methods

Compressions

Dimension arguments

Direct combinatorial arguments

Hilbert space arguments

The probabilistic method

Topological methods

What method should I use?

Prerequisites

A familiarity with basic definitions from graph theory and combinatorics.

General discussion

Consider the following five problems about collections of sets.

1. For which values of k,r and n is it possible to find a system \mathcal{A} of subsets of \{1,2,\dots,n\} such that every A in \mathcal{A} has size r and every subset B of \{1,2,\dots,n\} of size k is contained in precisely one set in \mathcal{A}?

2. Let 2k\leq n and let \mathcal{A} be a collection of subsets of \{1,2,\dots,n\} such that every set in \mathcal{A} has size k and no two sets in \mathcal{A} are disjoint? How big can \mathcal{A} be?

3. Suppose that \mathcal{A} is a collection of subsets of \{1,2,\dots,n\} such that every set A that belongs to \mathcal{A} has even size and the intersection of any two different sets in \mathcal{A} has odd size. How big can \mathcal{A} be?

4. Let n be even and suppose that \mathcal{A} is a collection of subsets of \{1,2,\dots,n\} such that every set in \mathcal{A} has size n/2 and the intersection of any two distinct sets in \mathcal{A} has size at most n/5. How big can \mathcal{A} be?

5. Let n be even and suppose that \mathcal{A} is a collection of subsets of \{1,2,\dots,n\} such that every set in \mathcal{A} has size n/2 and the intersection of any two distinct sets in \mathcal{A} has size at most n/3. How big can \mathcal{A} be?

6. Let n=2r+1, and let the subsets of \{1,2,\dots,n\} of size r be partitioned into m classes. How big does m need to be if no two disjoint sets lie in the same class?

There are strong superficial similarities between all these problems, but the techniques appropriate for solving them are radically different from problem to problem. The first one is closely related to results in algebra, the second can be tackled by clever purely combinatorial arguments, the third is best rephrased as a problem about vector spaces over \mathbb{F}_2, the fourth is more fruitfully regarded as a problem about unit vectors in Euclidean spaces, the fifth cannot be solved exactly but estimates can be obtained using tools from probability, and the solution to the sixth is an application of the Borsuk-Ulam theorem from topology.

Incidentally, if you think that the first problem looks rather different from the next four because the next four are about maximizing the size of a set system, consider the following reformulation: let k, r and n be positive integers with k<r<n. What is the maximum cardinality of a set system \mathcal{A} if every set in \mathcal{A} has size r and the intersection of any two distinct sets in \mathcal{A} has size at most k-1? In particular, does such a set system exist with size \binom nk/\binom rk? The second question is equivalent to question 1, since if such a system exists, then it has to cover all \binom nk sets of size k exactly once, and each set of size r covers \binom rk sets. And the converse clearly holds too.

Similarly, the last question can be more closely related to the others, though there is a sense in which it is genuinely distinct. One way that one might attempt to prove that m has to be large would be to show that all the classes have to be small, and that would again be a question of maximizing the size of a set system given assumptions about intersections. However, this approach does not give anything like the best bound: it really is a question about partitioning.