Tag Archives: Extremal combinatorics

Analysis of Boolean Functions – week 1

Home page of the course.

In the first lecture I defined the discrete n-dimensional cube and  Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets.

1) The largest possible intersecting family of subsets of [n];

2) The largest possible intersecting family of subsets of [n] so that the family of complements is also intersecting;

3) The largest possible family of graphs on v vertices such that each two graphs in the family contains a common triangle;

4) Chvatal’s conjecture regarding the maximum size of an intersecting family of sets contained in an ideal of sets;

5) Erdos-Ko-Rado Theorem.

Exercise: Prove one of the following

a) The Harris-Kleitman’s inequality

b) (from the H-K inequality) Every family of subsets of [n] with the property that every two sets have non-empty intersection and no full union contains at most 2^{n-2} sets.

More reading: this post :”Extremal combinatorics I: extremal problems on set systems“. Spoiler: The formulation of Chvatal’s conjecture but also the answer to the second exercise can be found on this post: Extremal combinatorics III: some basic theorems. (See also peoblen 25 in the 1972 paper Selected combinatorial research problems by Chvatal, Klarner and Knuth.)


I moved to discuss the problem of collective coin flipping and the notion of influence as defined by Ben-Or and Linial. I mentioned the Baton-passing protocol, the Alon-Naor result, and Feige’s two-rooms protocol.

More reading: this post :” Nati’s influence“. The original paper of Ben-Or Linial:  Collective coin flipping, M. Ben-Or  and N. Linial, in “Randomness and    Computation” (S. Micali ed.) Academic Press, New York, 1989, pp.    91-115.

Cup Sets, Sunflowers, and Matrix Multiplication

This post follows a recent paper On sunflowers  and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), and refers also to a paper by Don Coppersmith and Shmuel Winograd (CW90).

Three famous problems

The Erdos-Rado sunflower conjecture

The Erdos-Rado sunflower (Delta system) theorem and conjecture was already menioned in this post on extremal set theory.

A sunflower (a.k.a. Delta-system) of size r is a family of sets A_1, A_2, \dots, A_r such that every element that belongs to more than oneofthe sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that

Erdos-Rado sunflower theorem: There is a function f(k,r) so that every family \cal F of k-sets with more than f(k,r) members contains a sunflower of size r.

One of the most famous open problems in extremal combinatorics is:

The Erdos-Rado conjecture: Prove that f(k,r) \le c_r^k.

Here, c_r is a constant depending on r. This is most interesting already for r=3.

Three term arithmetic progressions

The cup set problem (three terms arithmetic progressions in (Z/3Z)^n):

The cup set problem was also discussed here quite extensively. (See, e.g. this post.)

Let \Gamma=\{0,1,2\}^n. The cap set problem  asks for the maximum number of elements in a subset of \Gamma which contains no arithmetic progression of size three or, alternatively, no three vectors that sum up to 0(modulo 3). (Such a set is called a cup set.) If A is a cap set of maximum size we can ask how the function h(n)=3^n/|A| behaves. Roy Meshulam proved, using Roth’s argument, that h(n) \ge n. Edell found an example of a cap set of size 2.2^n. So h(n) \le (3/2.2)^n.  The gap is exponential.

The strong cap set conjecture: h(n) \ge (1+\epsilon)^n for some \epsilon >0.

Of course, the cap set problem is closely related to

Erdos-Turan problem (for r=3): What is the larget size r_3(n) of a subest of {1,2,…,n} without 3-term arithmetic progression?

Matrix multiplications

Let ω be the smallest real number so that there is an algorithm for multiplying  two n \times n matrices which requires O(n^\omega ) arithmetic operations.

The ω=2 conjecture: ω=2.

A very recent breakthrough by Virginia Vassilevska Williams (independently) following an earlier breakthrough by Andrew Stothers improved the Coppersmith-Winograd algorithm which gave ω =2.376, to 2.374 and 2.373 respectively. (See the discussions over Lipton’s blog (1,2), Shtetl optimized, and Computational Complexity.)

It turns out that these three conjectures are related. (The connection of matrix multiplication and the Erdos-Turan problem is fairly old, but I am not sure what an even drastic improvment of Behrends’s lower bound would say about \omega.)

Three combinatorial conjectures that imply ω=2.

Remarkably, an affarmative answer for the ω=2 conjecture would folow from each one of three combinatorial conjectures. One conjecture goes back to CW90 and two were described in CKSU05. I will not present the precise formulations in order to encourage the readers to look at the original papers. (Maybe I will add the formulations later.)

The no disjoint equivoluminous subsets conjecture (CW90).

The Strong UPS conjecture (CKSU05).

Theorem: Conjecture CW90 implies the strong UPS conjecture.

CKSU’s two-family conjecture (CKSU05).

Relations between these problems

Here are some results taken from ASU11 about the relations between these combinatorial questions. The first result goes back to Erdos and Szemeredi.

The weak sunflower conjecture: A family \cal F of subsets of {1,2,…,n}  with no sunflower of size 3 can have at most (2-\epsilon)^n sets.

The following results are not difficult.

Theorem: The strong sunflower conjecture implies the weak sunflower conjecture.

Theorem: The strong cup set conjecture also implies the weak sunflower conjecture.

Theorem: The weak sunflower conjecture implies that the CW90 conjecture is false.

It follows that CW90 conjecture is in conflict both with the Erdos Rado sunflower conjecture and with the strong cup set conjecture.

Theorem: The strong cup set conjecture implies that the strong UPS conjecture is false.

While two family theorems are quite popular in extremal combinatorics (see this post and this one), CKSU’s two family conjecture is still rather isolated from other combinatorics.

What to believe?

This is a nice topic for discussion.

Extremal Combinatorics on Permutations


We talked about extremal problems for set systems: collections of subsets of an n element sets, – Sperner’s theorem, the Erdos-Ko-Rado theorem, and quite a few more. (See here, here and here.) What happens when we consider collections of permutations rather than collection of sets? Not so much is known on extremal problems for families of permutations.

David Ellis, Ehud Friedgut, and Haran Pilpel have recently proved an old conjecture of Deza and Frankl regarding an analog for permutations of the Erdos-Ko-Rado Theorem. They showed that for every k if n is sufficiently large, any family of permutations on an n-element set such that every two permutations in the family agree in at least k places, contains at most (n-k)! permutations.

The proof uses spectral methods and representations of the symmetric group.

Frankl-Rodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A)

Voita Rodl

I would like to tell you about a research project in progress with Roy Meshulam. (We started it in the summer, but then moved to other things;  so far there are interesting insights, and perhaps problems, but not substantial results. Noga Alon contributed an important observation, and Jeff Kahn and Gabor Simonyi helpful comments.)  

Roy and I are friends and have been discussing various mathematical problems for decades. In the last few years we have studied together topological Helly-type theorems and have written several papers together. Our most recent success was finding a topological version of a Helly-type theorem by Nina Amenta. This post is on another problem.

As always, and more so in the spirit of Nielsen’s and Gowers’s recent suggestions:  comments, ideas, related problems, lemmas, and discussions  are welcome.  Links or references to earlier works (published and unpublished) are also welcome.  I thought to wait with this story after I discuss the Frankl-Wilson theorem and the Frankl-Rodl theorem in my extremal combinatorics series. But as this project is somewhat related to the density Hales-Jewett project discussed over Gowers’s blog (and even more to this thread at Tao’s blog), I decided to go ahead with it.


Part A: Finding generalized solutions for the cap set problem

1. Modular-lines-free-subsets

Let n=3m. A modular line in T(n)= \{0,1,2\}^n is a set of  three elements x,y,z such that the number of coordinates i for which x_i + y_i + z_i =a is zero modulo m for a=0,1,2. (The sum x_i+y_i+z_i is taken modulo 3.)

Problem 1:  How large can a subset F of T(n) be without containing a modular line? Prove that |F| < (3-\epsilon)^n, for some constant \epsilon >0.

2. Why? avoiding lines (3-term arithmetic progressions) in Z_3^n..

The following is a well-known problem:

Problem 2: Find the largest size f(n) of a set A \subset Z_3^n without an arithmetic progression of size 3. In this case an arithmetic progression of size three is simply a sequence of three elements x, y and z such that x+y+z=0. In other words, an arithmetic progression is simply an affine line.

This problem was discussed by Frankl, Graham, and Rodl in 1987 (and perhaps was posed even earlier) and they showed that f(n)=o(3^n). Roy Meshulam proved that f(n) \le 3^n/n. This is a beautiful and clear application of Roth’s argument (for his famous theorem on the density of sets without 3-term arithmetic progressions,) for the case of subsets of \{1,2,\dots,n\}. Ten years ago Roy and I tried quite hard to push this Fourier-theoretic argument and to get a better bound, even slightly, even very slightly. We did not succeed. (And so far, nobody else has; a recent impressive result of Tom Sanders for 3-term arithmetic progressions without a repeated element for subsets of  Z_4^n gives reason for optimism.) Let us write f(n)=3^n/g(n). The best lower bound on g(n) is n. There is a construction of Edell showing that f(n) \ge2.2^n and thus the best upper bound for g(n) is more than 1.3^n. The gap is huge! What is the true value? Terry Tao wrote a lovely post on this problem. A set in Z_3^n without a 3-term arithmetic progression (or alternatively not containing an affine line) is called a cap set.

Let me mention that the set of 0-1 vectors of length n is a very simple example of a cap set of size 2^n; choosing a set at random works if the size is less than 3^{n/3}.   Problem 1 is a variation on problem 2.  Continue reading

Lovasz’s Two Families Theorem

Laci and Kati

Laci and Kati

This is the first of a few posts which are spin-offs of the extremal combinatorics series, especially of part III. Here we talk about Lovasz’s geometric two families theorem.



1. Lovasz’s two families theorem

Here is a very beautiful generalization of the two families theorem due to Lovasz. (You can find it in his 1977 paper Flats in Matroids and Geometric Graphs.)

Lovasz’s Theorem: Let V_1,V_2,\dots V_t and W_1, W_2, \dots , W_t be two families of linear spaces having the following properties:

1) for every i, \dim V_i \le k, and \dim W_i \le \ell.

2) For every i, V_i \cap W_i = \{0\},

3) for every i \ne j, V_i \cap W_j \ne \{0\}.

Then t \le {{k+\ell} \choose {k}}.

This theorem is interesting even if all vector spaces are subspaces of an (k+\ell)-dimensional space.

Recall Bollobas’s two families theorem: Continue reading

Extremal Combinatorics IV: Shifting




We describe now a nice proof technique called “shifting” or “compression” and mention a few more problems.


The Sauer-Shelah Lemma:

Let N=\{1,2,\dots,n\}. Recall that a family {\cal F} \subset 2^N shatters a set S \subset N if for every R \subset S there is T \in {\cal F}  such that S \cap T=R.

Theorem (Sauer-Shelah): If |{\cal F}| > {n \choose 0} + {n \choose 1} + \dots + {n \choose k} then there exists a set S, |S|=k+1, such that \cal F shatters S.

Proof by Shifting

I will describe now a proof of the Sauer-Shelah theorem which is not the easiest but still is quite easy and demonstrates an important technique called “shifting” or “compression” (for an application to additive number theory look at this post by Terry Tao).

The idea of shifting is to reduce an extremal problem for a family of sets \cal F to the case of families of a special type. In the case of the Sauer-Shelah Theorem we first make a reduction to families which are closed under taking subsets (such families are called “ideals,” “down-sets,” and “simplicial complexes”).  Then we prove the theorem for such families. Continue reading

Extremal Combinatorics III: Some Basic Theorems



Let us return to extremal problems for families of sets and describe several basic theorems and basic open problems. In the next part we will discuss a nice proof technique called “shifting” or “compression.”

The Sauer-Shelah (-Perles -Vapnik-Chervonenkis) Lemma:

(Here we write N = \{1,2,\dots,n\}.) A family {\cal F} \subset 2^N shatters a set S \subset N if for every R \subset S there is F \in {\cal F} such that S \cap F=R. Note that in order to shatter a set of size m  you need at least 2^m sets. But how many sets will guarantee that you shatter a set with m elements? The Sauer-Shelah Lemma answers this question!

Theorem (Sauer-Shelah): If  \cal F > {n \choose 0} + {n \choose 1} + \dots + {n \choose k}  then there exists a set S, |S|=k+1 such that \cal F shatters S.

Hmm LaTeX can go wild, let me try that again:

Theorem (Sauer-Shelah): If  |{\cal F}| > {n \choose 0} + {n \choose 1} + \dots + {n \choose k} then there exists a set S, |S|=k+1 such that \cal F shatters S.

(This is much better.)

The simplest way to prove this theorem is by induction. Here is a variation I just heard from Noga. Proof (a little sketchy): Prove a slightly stronger fact that every family \cal F shatters at least as many sets as |{\cal F}|. Consider the subfamily {\cal F}_0 of sets in the family not containing '1'. By induction {\cal F}_0 shatters at least as many subsets of N' = \{2,3, \dots , n\} as |{\cal F}_0|. Next consider {\cal F}_1 = \{S \in {\cal F}: 1 \in S\}, and {\cal F}'_1 = \{S \backslash \{1\}: S \in {\cal F}, 1 \in S \}.  By induction {\cal F}'_1 shatters as many subsets of \{2,3,\dots,n\} as its cardinality. The number of subsets of N' shattered by {\cal F}_0 and {\cal F}'_1 sum up to at least |{\cal F}_0|+|{\cal F}'_1| = |{\cal F}|, and every subset of N' shattered by {\cal F}'_1 is shattered by {\cal F}_1 \subset {\cal F}. Sababa? not quite! there may be subsets R \subset N' shattered by both {\cal F}_0 and {\cal F}'_1. But note that in this case both R and latex R \cup \{1\} are shattered by \cal F. walla!

OK, let me give a few more words of explanation about the proof. When I say “every family” do I mean “every family that satisfies the condition of the theorem?” (And If I do why can I use induction?) No, i really mean every family. The point is that if every family shatters  at least as many sets as its size then a family which satisfies  |{\cal F}| > {n \choose 0} + {n \choose 1} + \dots + {n \choose k} shatters more sets than this sum. But then it must shatter a set of size larger than k because there are not enough subsets of the set \{1,2,\dots,n\} of size at most k.

One additional word about the proof. Considering the sets containing ‘1’ and those not containing ‘1’ and then applying an inductive argument which can be simple or extremely complicated, direct or involving several additional methods, is a very basic proof method in extremal set theory. 

This theorem can be described as an “eigentheorem” because it is important in many different places. It was mentioned (with an algebraic proof by Frankl and Pach) in Gowers’ blog and also, in another context, in Kowalski’s blog. Sauer proved it in response to a problem of Erdos. Shelah (with Perles) proved it as a useful lemma for Shelah’s theory of stable models. (At some later time, Benjy Weiss asked Perles about such a result in the context of ergodic theory and Perles who forgot that he proved it once proved it again.) Vapnik and Chervonenkis proved it in the context of statistical learning theory. The VC-dimension of a family of sets is the size of the largest set the family shatters. This notion plays an important role in learning theory, statistics and probability theory. There are several applications of the Sauer-Shelah theorem to analysis and to the geometry of Banach spaces, and there are several extensions and refinements.

The Kruskal-Katona Theorem

We let \bf N denote the set of positive integers and let {{\bf N} \choose {k}}  = \{S: S \subset {\bf N}, |S|=k\}.

Let {\cal F} be a subset of {{\bf N} \choose {k}}. The Shadow \partial {\cal F} is the set of all (k-1)-subsets of \bf N  which are contained in at least one set in \cal F.

We would like to answer the following question. How small can the Shadow of a family of m k-sets be? The precise answer to this question is given by the Kruskal-Katona’s theorem.

Continue reading