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.

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.