Skip to main content
4 of 4
replaced http://mathoverflow.net/ with https://mathoverflow.net/

About hyperplanes cutting the discrete hypercube

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

gradstudent
  • 2.2k
  • 16
  • 28