5
$\begingroup$

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.

$\endgroup$

1 Answer 1

9
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I haven't done the calculations carefully (at all), but I guess you only expect to find $C\log n$ faces mostly contained (with the $C$ probably depending on how much you want contained). $\endgroup$ Jan 3, 2013 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.