1
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you mean a hyperplane through the origin? Otherwise, there's no such thing as a random hyperplane. $\endgroup$
    – Robert Israel
    Commented Feb 13, 2017 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
    Commented Feb 13, 2017 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
    Commented Feb 13, 2017 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
    Commented Feb 13, 2017 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
    Commented Feb 14, 2017 at 1:16

0

Reset to default

You must log in to answer this question.