Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Since my intuition for high dimensional geometry is not always right:

Consider the unit cube in $\mathbb{R}^m$ and for $n\leq m$ denote by $F^n$ the union of the $n$-facets. For what numbers of $m$ and $n$ does any $n$-dimensional subspace of $\mathbb{R}^m$ intersect $F^n$?

Extra: Consider the same question for $G^n$ = $F^n\setminus F^{n-1}$.

(P.S: What kind geometry tag would be appropriate?)

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

The condition for the first question is: $2n \geq m.$

share|improve this answer
    
Oh, cool. Any reference? –  Dirk Dec 7 '11 at 20:37
    
Not specifically for that fact, but you can check out my paper "Asymptotic geometry of convex sets in $H^n$ and $E^n,$ motivated by this very fact" (arxiv.org or Advances in Math, the latter has slightly fewer typos). –  Igor Rivin Dec 7 '11 at 20:41
add comment

Here's a way of thinking about Igor's answer to the first part:

Consider first a "generic" $n-$dimensional subspace defined by a system of $m-n$ equations. For any particular $n-$facet, being on that facet means you only have $n$ free variables. So if $n< m-n$, there isn't really any hope to satisfy all the equations at once.

Conversely, if you have a subspace satisfying $m-n \leq n$, you can imagine the following process. We will refer to a variable as fixed if its value is equal to $1$ or $-1$, and free otherwise.

We start at the point $v=0$, at which point all variables are free. If at any point there are fewer than $m-n$ free variables, then there must be a $w \neq 0$ in the subspace which is equal to $0$ at all fixed variables (here we're using $m-n \leq n$). We can then replace $v$ by $v+\lambda w$, where $\lambda$ is chosen to be as large as possible subject to the constraint that we still lie in the hypercube. This new vector is still in the subspace, and has (at least) one more fixed variable than before.

share|improve this answer
    
Thanks! That even allows to calculate a sample point in the intersection fairly easy. May I ask: Can one gain more information about the intersection, e.g. enumerate the facets which lie in the intersection? Is that problem hard? –  Dirk Dec 14 '11 at 14:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.