Extremal Combinatorics I: Extremal Problems on Set Systems

Posted on May 1, 2008 by Gil Kalai

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

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

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

  1. alef says:
    May 4, 2008 at 6:10 pm

    took should be tool

    Reply

  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

  11. Anurag Bishnoi says:
    January 12, 2015 at 2:36 am

    Perhaps it should be noted that the dimension argument can be easily modified to prove a stronger version of the Fisher’s/deBruijn Erdös theorem, the non-uniform Fisher’s inequality: http://www.sciencedirect.com/science/article/pii/0012365X87901063

    Reply

  12. Pingback: Updates and plans III. | Combinatorics and more

  13. Pingback: Around the Garsia-Stanley’s Partitioning Conjecture | Combinatorics and more

  14. Pingback: Touching Simplices and Polytopes: Perles’ argument | Combinatorics and more

  15. Pingback: Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture | Combinatorics and more

  16. Pingback: Preview: The solution by Keller and Lifshitz to several open problems in extremal combinatorics | Combinatorics and more

  17. Pingback: Extremal Combinatorics V: POSETS | Combinatorics and more

  18. Yizhou Guo says:
    October 13, 2022 at 7:35 am

    Dear Professor Kilai,

    In summer of 2021, with the aim of composing an olympiad style problem, it occurred to me that one could use pidgeonhole principle to prove that for $n$-set $S$, any subset of $\mathcal{P}(S)$ with cardinality greater than $\binom{n}{n/2}$ must contain two elements such that one is less than the other under the partial order of set inclusion. I only learned yesterday that this is actually the harder direction of what is now conventionally known as Sperner’s theorem.

    The proof I constructed is as follows.
    __________________________________________________________
    Let $[n]_k$ denote the $k$-subsets of $\{1,2,\ldots, n\}$. For any $0 \leq k 1$ and that the inductive hypothesis holds for $n-1$. If $X \in [n]_k$ does not contain $n$, set
    $$i_{n,k}(X)=i_{n-1,k}(X).$$
    If it does contain $n$, set
    $$i_{n,k}(X)=i_{n-1,k-1}(X \setminus \{n\}) \cup \{n\}.$$
    By 2-partitioning by containment of $n$ and our inductive hypothesis, this is necessarily an injection.

    In the case of $n,k$ such that $2k+1=n$, one can transition to $k+1$ by using inductive hypothesis as above, or with $\binom{n}{k}=\binom{n}{k+1}$, we can construct a corresponding $k+1$-regular bipartite graph with the $k$-sets and $k+1$-sets as the two parts and an edge iff there is an inclusion relation and apply Hall’s theorem to prove the existence of an inclusion preserving bijection.

    By symmetry, we also have for $k > \lceil n/2\rceil$ injections $j_{n,k}: [n]_{k} \to [n]_{k-1}$.

    We now repeat the following procedure, starting with $\mathcal{P}([n])$ as our set of available tokens:

    1. Set `cur` to any token minimum in cardinality among the available ones.
    2. Mark value of `cur` as unavailable and execute $cur <- i_{n,k}(cur)$; keeping during this until `cur` has cardinality equal to $\lceil n/2 \rceil$. Existence of injections up to this point means this is achievable.
    3. If $j_{n,k}^{-1}(cur)$ is non-empty (the inverse of injection also cannot contain multiple elements), set `cur` to it, while marking its previous value as unavailable. Do this until the preimage is empty.
    4. Add this chain generated by steps 2,3 to our collection of chains
    5. Repeat 2-4

    It is not difficult to prove that the algorithm described above results in a partition of $\mathcal{P}([n])$ into $\binom{n}{\lfloor n/2\rfloor}$ chains. The result then follows from the pidgeonhole principle.
    __________________________________________________________
    Via Wikipedia, I was brought to take a quick look at Lubell 1966 (https://sci-hub.se/10.1016/S0021-9800(66)80035-2) and Erdos 1945 (https://sci-hub.se/10.1090/S0002-9904-1945-08454-7). I was surprised that Lubell actually published in Journal of Combinatorial Theory a half page proof of this. This makes me wonder if the proof that I independently thought of had been published before (I would bet that someone had thought of a proof using more or less the same idea before.)

    I never actually studied any Erdos style combinatorics, being more inclined to theory-building based mathematics. It was only yesterday that I learned that Hall's theorem (which I had heard of before but never remembered its statement) is fittingly used to prove existence of perfect matchings. Moreover, it was only yesterday that I learned the statement of the Erdos-Ko-Rado theorem, though I had heard the name before.

    Certainly, your feedback would be much welcome.

    Thank you!
    Yizhou Guo

    Reply

Leave a comment