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.

Update (Oct 2010): Problem III should be referred to as the Siminovits-Sos conjecture. It was made by Simonovits and Sos in 1976. The conjecture was proved by Ellis, Filmus, and Friedgut in 2010.

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.

Update: This proof is an example of “dimension arguments in combinatorics”. For more examples and a general discussion see this post in Gowers’s weblog.

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.)

About these ads
This entry was posted in Open problems and tagged , , , , , . Bookmark the permalink.

10 Responses to Extremal Combinatorics I: Extremal Problems on Set Systems

  1. alef says:

    took should be tool

  2. Pingback: Local Events, Turan’s Problem and Limits of Graphs and Hypergraphs « Combinatorics and more

  3. Pingback: Extermal Combinatorics II: Some Geometry and Number Theory « Combinatorics and more

  4. Pingback: Plans and Updates « Combinatorics and more

  5. Pingback: Extremal Combinatorics III: Some Basic Theorems « Combinatorics and more

  6. Pingback: Mathematics, Science, and Blogs « Combinatorics and more

  7. Pingback: Extremal Combinatorics on Permutations « Combinatorics and more

  8. Pingback: The Simonovits-Sos Conjecture was Proved by Ellis, Filmus and Friedgut | Combinatorics and more

  9. Pingback: Tentative Plans and Belated Updates II | Combinatorics and more

  10. Pingback: Analysis of Boolean Functions – week 1 | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s