Given $\{-1,1\}^n$ we randomly choose a hyperplane in $\mathbb{R}^n$. Now given an integer $p \in [1,n]$ and a number $\epsilon \in [0,1]$, I want to ask, "How likely is it that at least one of the $p-$dimensional faces of the discrete hypercube gets sliced by this plane and has $< \epsilon$ fraction of points on either of the linear fragments so produced on that face?"

  • Is this question well defined?
  • Do we know anything about this?

Somewhat related previous MO discussions, faces in the discrete cube and Partitioning the vertices of an n-cube with random hyperplane cuts and Directed Hypercube Minimal Cuts

  • $\begingroup$ Do you mean a hyperplane through the origin? Otherwise, there's no such thing as a random hyperplane. $\endgroup$ – Robert Israel Feb 13 '17 at 19:33
  • $\begingroup$ By "hyperplane" I mean any affine space. Consider any function of the form, $\vec{a}.\vec{x}+b =0$. $\endgroup$ – gradstudent Feb 13 '17 at 20:22
  • 2
    $\begingroup$ In that case, there is no uniform random choice. You would need to specify the distribution. And if that distribution allows $b$ to be large compared to $|\vec{a}|$, it is very likely that the hyperplane will miss your hypercube entirely. $\endgroup$ – Robert Israel Feb 13 '17 at 20:53
  • $\begingroup$ Maybe this is a way to think of what I am trying to convey : Fix the choice of $\vec{a}$ and $\vec{b}$. Now can one show that there is an universal upper bound on the probabilities I am looking for? (...for example see what happens in say the Sperner's Theorem..there is an universal upperbound on the number of solutions of a linear equation on the discrete hypercube and that upperbound doesn't depend on the $\vec{a}$ or $b$ that one starts with..) $\endgroup$ – gradstudent Feb 13 '17 at 22:10
  • $\begingroup$ That still doesn't make sense to talk about "probability." As for extremal bounds, some hyperplanes (e.g., $x_1 =1$) contain faces entirely, and some (e.g., $x_1 =0$) cut things in half very neatly. What more specifically are you really trying to ask? (Perhaps it would help us understand what you want if you describe your motivation.) $\endgroup$ – Pat Devlin Feb 14 '17 at 1:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.