5
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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
    Commented Jan 20, 2018 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
    Commented Jan 23, 2018 at 23:11

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jan 23, 2018 at 23:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .