Extremal Combinatorics I: Extremal Problems on Set Systems

The “basic notion seminar” is an initiative of David Kazhdan who joined HU math department around 2000. People give series of lectures about basic mathematics (or not so basic at times). Usually, speakers do not talk about their own research and not even always about their field. I gave two lecture series, one about “computational complexity theory” a couple of years ago, and one about extremal combinatorics or Erdös-type combinatorics a few months ago, which later I expanded to a series of five+one talks at Yale. One talk was on the Borsuk Conjecture, which I will discuss separately, and five were titled: “Extremal Combinatorics: A working tool in mathematics and computer science.” Let me try blogging about it. The first talk was devoted to extremal problems concerning systems of sets.

Paul Erdös

1. Three warm up problems

Here is how we move very quickly from very easy problems to very hard problems with a similar flavour.

Problem I: Let N = {1,2, … , n } . What is the largest size of a family $\cal F$ of subsets of $N$ such that every two sets in $\cal F$ have non empty intersection? (Such a family is called intersecting.)

Answer I: The maximum is $2^{n-1}$ . You can achieve it by taking all subsets containing the element ‘1′. You cannot achieve more because from every pair of a set and its complement, you may choose only one set to the family.

Problem II: What is the largest size of a family $\cal F$ of subsets of $N$ such that every two sets in $\cal F$ their union is not $N$ .

You can protest and claim that Problem II is just the same as Problem I. Just move to complements. Or just use the same answer. OK, lets have another Problem II, then.

New Problem II: What is the largest size of a family $\cal F$ of subsets of $N$ such that for every two sets $S,R$ in $\cal F$ their intersection is non empty and their union is not $N$ .

An example of such a family is the set of all sets containing the element ‘1′ and missing the element ‘2′. This family has $2^{n-2}$ sets. It took several years from the time this problem was posed by Erdös untill Kleitman showed that there is no larger family with this property.

Problem III (Erdös-Sos Conjecture) Let $\cal F$ be a family of graphs with N as the set of vertices. Suppose that every two graphs in the family have a triangle in common. How large can $\cal F$ be?

Now, the total number of graphs on n vertices is $2 ^{{{n} \choose {2}}}$ . (Note: we count labelled graphs and not isomorphism types of graphs.) A simple example of a family of graphs with the required property is all the graphs containing a fixed triangle. Say all graphs containing the edges {1,2},{1,3},{2,3}. This family contains 1/8 of all of graphs. Is there any larger family of graphs with the required property? Erdös and Sos conjectured that the answer is no - you cannot get a larger family. This conjecture is still open.

Vera Sos

2. Two basic theorems about families with prescribed intersections.

Erdös-Ko-Rado Theorem: An intersecting of k-subsets of $N$ , when $2k \le n$ contains at most ${{n-1} \choose {k-1}}$ sets.

Fisher; deBruijn-Erdös Thorem: A family of subsets of $N$ so that every two (different) sets in the family have precisely a single element in common has cardinality at most n.

(Erdös and deBruijn concluded that n non colinear points in the plane determine at least n line. Try to deduce it!)

All k-subsets of N containing the element ‘1′ is an example of equality for the Erdos-Ko-Rado theorem. For the Erdös deBruijn take the family {{1} , {1,2} {1,3} … {1,n}} or replace the first set by {2,3,…,n}, or take a finite projective plane.

Fano plane the finite projective place of order 2.

3. The linear algebra proof of deBruijn Erdös Theorem.

The linear algebra proof of the Fisher; de Bruijn-Erdös Theorem goes roughly as follows: Suppose that there are m sets in the family $A_1,A_2,\dots, A_m$ . Consider the incidence matrix of the family: The (i,j)-entry in this matrix is ‘1′ if i belongs to $A_j$ .

The crucial fact is that the columns $c_1,c_2,\dots, c_m$ of the incidence matrix are linearly independent. This gives $m \le n$ .

How do we go about proving that the columns are linearly independent? We first assume that all sets have cardinality at least 2. Then we write $s = \sum \alpha_i c_i$ , and compute the inner product

$<s,s>=\sum \sum \alpha_i \alpha _j <c_i , c_j>$ .

We note that if i and j are distinct $<c_i,c_j>=1$ and that $<c_i,c_i>=|A_i|$ .

And write $<s,s>= \sum_{i=1}^m \alpha_i^2 (|A_i|-1) + (\sum_{i=1}^m \alpha_i)^2$ .

This can vanish only if all coefficients $\alpha_i$ are equal to 0.

4. Sperner’s theorem

(I wanted to indicate how Erdös-Ko-Rado theorem is proved. There are various proofs and for the two proofs I like to give it is better to demonstrate the proof technique in a simple case.)

Sperner’s theorem fron 1927 asserts that the maximum size of a family $\cal F$ of subsets of N which is an antichain with respect to inclusion is the middle binomial coefficient ${{n} \choose {n/2}}$ . Lubell found a simple nice proof for Sperner’s theorem: Let $\cal F$ be such an antichain and suppose that it has $s_k$ sets of cardinality k. Count pairs $(\pi, S)$ where $\pi$ = $((\pi(1),\pi(2), \dots , \pi(n))$ is a permutation of {1,2, … ,n} and S is a set in the family which is initial w.r.t. $\pi$ , namely S={ $\pi(1), \pi(2),\dots,\pi(k)$ } for some k. Now, for every permutation $\pi$ you can find at most one initial S in the family $\cal F$ (because of the untichain condition). If S is a set of k elements, you can find precisely k! (n-k)! permutations $\pi$ for which S is initial. Putting these two facts together we get that $\sum_{k=0}^n s_k k! (n-k)! \le n!$ or in other words $\sum_{k=0}^n s_k/ {{n} \choose {k}} \le1$ . This inequality (called the LYM inequality) implies the required result.

Bella Bollobas, one of the discoverers of the LYM inequality.

There is a similar proof for Erdös-Ko-Rado’s theorem

The idea is to count pairs $(\pi,S)$ where $S$ is a set in the family, $\pi$ is a circular permutation $(\pi(1),\pi(2), \dots , \pi(n))$ and $S$ is a continuous “interval” with respect tp $\pi$ .

On the one hand there are (n-1)! cyclical permutations and as it is not hard to see for each such permutation, you can get at most k “intervals” which are pairwise intersecting. On the other hand, for every set S there are k!(n-k)! cyclic permutations on which S is a continuous interval.

So $|\cal F|$ k! (n-k)! $\le (n-1)! k$ and this gives the Erdös Ko Rado theorem.

What about the “not hard to see part”. This uses the fact that $2k \le n$ . One way about it is to consider the interval J whose left most element z is furthest to the left and notice that there are k intervals that intersect J whose left most element is right of z. Another way is to consider some interval J of length k and notice that the 2k-2 intervals intersecting it come in (k-1) pairs where each pair contains two disjoint intervals.

5. Turan’s theorem and Turan’s problem

The special case of Turan’s theorem for graphs with no triangles was proved by Mantel in 1907

The maximum number $t_2(n)$ of edges in a graph on n vertices without a triangle is attained by a complete multi-partite graph with n vertices where the sizes of the parts are as equal as possible.

The full Turan’s theorem was proved in the 40s.

The maximum number $t_r(n)$ of edges in a graph on n vertices which does not contain a complete subgraph with (r+1) vertices is attained by a complete multi-partite graph with n vertices where the sizes of the parts are as equal as possible.

Paul Turan

Proving Turan’s theorem: It is difficult not to prove Turan’s theorem; it seems that every approach to proving it succeeds. One approach is this: for simplicity consider the case of triangles. Take a vertex with maximum degree and divide the other vertices of the graph into two parts: A - the neighbors of v, B - the remaining vertices. Now, note that the vertices in A form an independent set (i.e. there are no edges between vertices in A). For every vertex in B delete all edges containing it and instead, connect it to all edges in A. Note that in the new graph, the degree of every vertex is at least as large as in the original graph. And, in addition, the new graph is bipartite. (One part is A.) It is left to show that for a bipartite graph the number of egdes is maximum, when the parts are as equal as possible.

Here is another proof. Delete a vertex from a graph G with n+1 vertices without $K_r$ . The number of edges in the remaining graph is at most $t_r(n)$ . Do it for all vertices and note that every edge is counted n-1 times. You get that the number of edges in G (hence $t_r(n+1)$ ) is at least the upper integral part of $t_r(n) \cdot (n+1)/(n-1)$ . Lo and behold this gives the right formula.

So let us conclude with Turan’s 1940 problem. You want to know what is the maximum cardinality of a set of triples from {1,2,…,n} which does not contain a “tetrahedron”, namely four triples of the form {a,b,c},{a,b,d),{a,c,d},{b,c,d}.

If you do not know it already; try to guess and suggest the best example. Turan made a conjecture which is still open.

(May 4, a few typos corrected, thanks alef and mike.)

Tags: Extremal combinatorics, Open problems

This entry was posted on May 1, 2008 at 7:37 am and is filed under Combinatorics:extremal, Open problems. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “Extremal Combinatorics I: Extremal Problems on Set Systems”

alef Says:
May 4, 2008 at 6:10 pm
took should be tool
Local Events, Turan’s Problem and Limits of Graphs and Hypergraphs « Combinatorics and more Says:
May 22, 2008 at 8:33 am
[...] the post regarding extremal combinatorics I left it to the readers to guess a conjecture on collections of [...]
Extermal Combinatorics II: Some Geometry and Number Theory « Combinatorics and more Says:
July 17, 2008 at 10:24 pm
[...] first lecture dealt with extremal problems for families of sets. In this lecture we will consider extremal [...]

Combinatorics and more