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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.