faces in the discrete cube

Question

This arose from a question Gil Kalai asked about a problem I posed involving the Fourier transform on the discrete cube. Maybe it is more tractable. I'm afraid I'm not sure how to do this kind of computation.

A $k$-dimensional face of the discrete cube $\{0,1\}^n$ is a set of the form: all vertices which take prescribed values (either $0$ or $1$) on some given $n-k$ coordinates and are otherwise arbitrary.

The question is: does a typical subset of $\{0,1\}^n$ approximately contain a face of dimension greater than $.6n$?

We are interested in the limit as $n\to\infty$. So "approximately contains" means "contains all but a fraction which goes to $0$ as $n\to\infty$". And "typical subset" means that as $n\to\infty$ the fraction of subsets for which this fails goes to zero. The $.6n$ can be moved a bit closer to $.5n$ but I am assuming this is not crucial.

A positive answer to this question would imply a generically positive answer to the Fourier transform question.

Answer 1

No. The typical set doesn't contain anything like a 0.6n face. Some similar questions are considered in "The Probabilistic Method" by Alon and Spencer (which I thoroughly recommend).

Here is the calculation. Let's just deal with 0.5n faces. I want to make a crude estimate of the probability that a subset (chosen uniformly) contains 90% of a 0.5n face.

The bound I'll use is the union bound: there are $\binom{n}{0.5n} 2^{n/2}$ $0.5n$-faces (choose which indices you want to restrict, and then decide the values you want to give them). This is considerably less than $2^{2n}$.

Now what is the probability that a random subset has density at least 90% in a given 0.5$n$-face?

I'll compute the probability that a random subset has density exactly 90% in a given 0.5$n$-face, since as you increase the density, the probability decays geometrically, so the first term dominates.

Since there are $2^{n/2}$ elements in the face, we're now asking for $$ \binom{2^{n/2}}{0.1\times 2^{n/2}}2^{-2^{n/2}}. $$ This is the number of ways of having exactly $0.9\times 2^{n/2}$ ones out of the $2^{n/2}$ possibilities (assume all numbers are integers by taking floors). A liberal dose of Stirling's formula shows that the binomial coefficient is $(0.1^{0.1}0.9^{0.9})^{-2^{n/2}}/2^{n/4}$ up to multiplicative constants, so that the number of configurations we're looking for is essentially $(0.1^{0.1}0.9^{0.9}\times 2)^{-2^{n/2}}/2^{n/4}$.

Since $0.1^{0.1}0.9^{0.9}>\frac12$, this decays fast (even when multiplied by $2^{2n}$).