I'd like to say that a large structured subset of the $n$-dimensional Boolean cube $\{0,1\}^n$ contains a non-trivial affine subspace. To be more specific, I want to prove/disprove that for some function $d=d(n)\gg\log(n)$ the following holds. If one partitions the $n$-dimensional Boolean cube into $2^{n-d}$ affine subspaces of dimension $d$, and then takes a half of these subspaces, then their union must contain an affine subspace of dimension $d+1$.

For $d < \log(n)-O(1)$ the statement holds just because each large subset of the Boolean cube always contains an affine subspace of dimension $\log(n)-O(1)$. For large subsets without any structure this logarithmic bound is essentially tight, since a counting argument shows that a random subset doesn't contain larger affine subspaces.

I'm wondering if the aforementioned structure of the set lets us find larger subspaces. I would appreciate any references to similar results (e.g., a disjoint union of arithmetic progressions of length d contains a longer arithmetic progression etc).

  • 1
    $\begingroup$ Let $e=n-d.$ Then the property you want to prove or disprove always fails for $e=1$ and sometimes (in $4/5$ of the cases?) for $e=2.$ $\endgroup$ – Aaron Meyerowitz Jan 20 '18 at 19:19
  • $\begingroup$ Right, this property trivially holds for $d<\log{n}$ and doesn't necessarily hold when $d$ is close to $n$. I'm wondering about the intermediate regime. For example, does it always hold for $d=\mathrm{poly}(\log{n})$? $\endgroup$ – Alex Golovnev Jan 23 '18 at 23:11

Interesting question. One thing I would try is to look on a random linear decision tree of depth n-d, and then take any other leaf in your union. I am guessing that this would give negative results for large enough d.

  • $\begingroup$ Hi Shachar, thanks! Is there a simple way to analyze random parity decision trees? I currently don't see even how to handle the case $d=(1-\varepsilon)n$. $\endgroup$ – Alex Golovnev Jan 23 '18 at 23:09

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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