Extremal combinatorics front page

a repository of mathematical know-how

Extremal combinatorics front page

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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 [[w:Turán's_theorem|Tur\'an'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.

[PREREQUISITES]

A familiarity with basic definitions from graph theory and combinatorics.

=== Some important methods in extremal combinatorics ===

[[Algebraic methods]]

[[Turn sets into functions|The analytic approach: turn sets into functions]] [cut] Quick description || A technique that is often useful in extremal combinatorics is to replace sets by their characteristic functions. What does this achieve? Well, sometimes it is possible to generalize the statement that one is trying to prove so that it applies not just to $\{0,1\}$-valued functions but to functions with values in larger sets such as $[0,1]$, $\mathbb{R}$ or $\mathbb{C}$. And these generalizations often turn out to be more natural than the original statements and therefore easier to prove. They also allow one to apply a wider range of techniques.[/cut]

[[Compressions]]

[[Dimension arguments in combinatorics|Dimension arguments]] [cut] Quick description || If you want to find the maximum of a combinatorial quantity, and if the maximum seems to be very far from unique, then try to relate the quantity to the dimension of a certain vector space.[/cut]

[[Direct combinatorial arguments in extremal combinatorics|Direct combinatorial arguments]]

[[Fourier techniques in combinatorics|Fourier techniques]]

[[Hilbert space arguments in combinatorics|Hilbert space arguments]]

[[Applying the probabilistic method|The probabilistic method]] [cut] Quick description || If you are trying to optimize a parameter associated with a combinatorial structure, and if the extremal examples appear to be highly "spread about" and unstructured, then you may well do best to consider examples that have been generated randomly. You are unlikely to prove an exact formula this way, but impressively sharp results can be obtained, often of results that nobody knows how to prove in any other way. [/cut]

[[Quasirandomness]]

[[Topological methods]]

=== Which of the above methods is the best one to use? ===

==== Six Examples ====

Consider the following six 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 odd size and the intersection of any two different sets in $\mathcal{A}$ has even 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 (see Example 4 of [[Double counting|this argument on double counting]] for a solution), the third is best rephrased as a problem about vector spaces over $\mathbb{F}_2$ (a solution is explained in Example 1 of [[Dimension arguments in combinatorics|this article about dimension arguments]]), the fourth is more fruitfully regarded as a problem about unit vectors in Euclidean spaces (as is explained in Example 1 of [[Turn sets into functions|this article on the analytic approach to extremal problems]]), 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 [[w:Borsuk-Ulam_theorem|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.

[GENERAL DISCUSSION]

If six such similar problems can need such different techniques for their solutions, is there any good way of predicting in advance, when one is faced with a problem in extremal combinatorics, which technique is most likely to work? If one could give a straightforward algorithm for this, then extremal combinatorics would be a duller subject than it is, but there are certainly some useful principles that can help one settle more quickly on a good technique.

A good general piece of advice to start with is to think hard about what you believe the extreme examples should look like.  This can make a big difference to how best to tackle the problem. For example, consider the difference between [[w:Ramsey_theory|Ramsey's theorem]] and [[w:Turan's_theorem|Turán's theorem]]. To be continued ...

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Extremal combinatorics front page

Recent articles

Active forum topics

Recent comments