Upper Bound for Vertices of Intersection of Subspace and Simplex

557 Views Asked by At

Let $S$ be a simplex in $\mathbb R^m$. It can be expressed as the convex hull of the columns of some affinely independent $m \times m + 1$ matrix $A$:

$$S=\left\{A\vec\alpha: \vec\alpha\in\mathbb R^{m+1},\alpha_i\ge0,\sum\alpha_i=1\right\}$$

Or alternately by the intersection of a set of $m + 1$ half-spaces defined by the rows of a matrix $C$, where each row $\vec c$ gives $\vec c^T \vec x \le 1$. (This requires that the origin be in the interior of the simplex, but that can be done without loss of generality).

$$S=\left\{\vec x\in\mathbb R^{m}:C\vec x\leqq 1\right\}$$

Let $Q$ be a subspace of dimension $n<m$, expressed in terms of a linearly independent basis:

$$Q=span\left\{\vec v_1,\vec v_2,...,\vec v_n\right\}=\left\{V\vec y:\vec y\in\mathbb R^n\right\}$$

If the intersection $Q\cap S$ contains a point in the interior of $S$, then it can be expressed as a convex hull in $Q$. From low dimensional cases, it is clear that there are some restrictions on its geometry. In particular, I am interested in the number of vertices. I believe the best lower bound is $n+1$; that is the minimum for any convex hull in $n$ dimensions, and one can be obtained in any dimension by construction. The the upper bound is much less clear.

At $m=3, n=2$ (a plane intersecting a tetrahedron), the lower bound is 3 and the upper bound is 4, since the planar cross sections of a tetrahedron are either triangles or quadrilaterals. However, it's not clear to me how this argument generalizes to higher dimensions.

The best general upper bound I could come up with is $\binom{m+1}{n}$, which follows from this argument:

The set of $\vec y$ coordinates has the same topology as the hull in $\mathbb R^m$, so we can look at the hull in that space, again assuming that the origin is an interior point.

$$Q\cap S = \left\{V\vec y: \vec y \in \mathbb R^n, CV\vec y\leqq 1\right\}$$

$CV$ is an $m+1\times n$ matrix, so this equation describes the intersection of $m+1$ half spaces in $\mathbb R^n$. Some of them could be redundant, but we can assume that none are to obtain an upper bound on vertices. Since this hull exists in $n$ dimensions, each vertex lies at the intersection of the boundaries of at least $n$ half spaces in order to be fully determined. If it is in the intersection of more than $n$ half spaces, we can find a subset of exactly $n$ whose intersection is the vertex. Thus if we consider every combination of $n$ half spaces, we will obtain all the vertices, which gives an upper bound of $\binom{m + 1}{n}$ vertices.

It seems like there ought to exist a better upper bound. This one gives more vertices than can possibly be attained for the low dimensional cases $(m=2, n=1)$, $(m=3, n=1)$, and($m=3, n=2)$.

Any input on how best to improve this bound (or show it can't be inproved) would be much appreciated. A more general result would be preferred, but I'm primarily interested in the case $m>>n>>1$.

1

There are 1 best solutions below

0
On

A better bound is $\left\lfloor\frac{(m+1)^2}{4}\right\rfloor$. I think it is valid for all $n\le m-1$ and it is definitely attained if $n=m-1$. For $n<m-1$ I don't have a better upper bound, but there should be one.

Assume $n=m-1$. In that case any $n$-plane is an hyperplane, so it is given by an equation $f(x_1,\dots,x_m)=a_1 x_1+\dots+a_m x_m=r$ for some $a_1,\dots,a_m$ and some $r$. Let the vertices of the $m$-simplex be $e_0,\dots,e_m$. Assume there are $k_1$ vertices with $f(e_i)>r$, there are $k_2$ vertices with $f(e_i)=r$ and $k_3$ vertices with $f(e_i)<r$. All the vertices of the intersection of the $m$-simplex $S_m$ with the hyperplane are either vertices of $S_m$ (so we have $k_2$ vertices of that type), or are the intersection of the straight line connecting a vertex $e_i$ with $f(e_i)>r$ with a vertex $e_j$ with $f(e_j)<r$, hence there are $k_1\cdot k_3$ vertices of that type.

So the intersection has $k_1\cdot k_3+ k_2$ vertices, hence an upper bound is given by $$ \max\{k_1\cdot k_3+k_2,s.t. k_1+k_2+k_3=m+1\}. $$ This maximum clearly is attained when $k_2=0$ (since $k_1(k_2+k_3)> k_1k_3+k_2$ if $k_1>1$) and so we have to maximize $k(m+1-k)$ for $k=0,\dots,m+1$. When $m+1$ is even, the maximum is at $k=\frac{m+1}2$ and is equal to $\frac{(m+1)^2}{4}$, and when $m+1$ is odd the maximum is attained at $k=\frac{m}2$ or $k=\frac m2+1$ and is equal to $\frac m2\left(\frac m2+1\right)=\frac{m(m+2)}{4}=\frac{(m+1)^2-1}{4}$.

So in both cases the maximum value is $\left\lfloor\frac{(m+1)^2}{4}\right\rfloor$.

It is also clear that for an hyperplane in general position $f(x)=r$ one can choose the constant $r$ such that $k_1$ vertices are on one side and $k_2$ vertices are on the other side of the hyperplane for any $k_1$ and $k_2$ with $k_1+k_2=m+1$. So there are hyperplanes for which the upper bound is attained.

Each $n$-plane is contained in an $m-1$ plane if $n\le m-1$, but that doesn't automatically implies that the same bound is valid for $n<m-1$. It should be so, but at the moment I have no proof.