Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
Thank you, that makes sense. –  Nik Weaver Jan 3 '13 at 1:01
    
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). –  Anthony Quas Jan 3 '13 at 2:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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