This arose from a question Gil Kalai asked about a problem I posed involving [the Fourier transform on the discrete cube](https://mathoverflow.net/questions/117754/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.



faces in the discrete cube
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}$). 


