1
$\begingroup$

Motivation:

This is related to a different question I asked in April. It occurred to me while thinking about the sums of uniform random variables and it stuck in my mind because it's the special case of a more general problem:

Given the hyperplane cut of $[-1,1]^N$,$H_{N}=\{\vec{x} \in [-1,1]^N:\sum_{i=1}^N x_i = 0\}$, what is the vertex set of $H_N$?

which reduces to the original question when $N \in 2\mathbb{N}$.

 My conjecture for this problem:

I conjecture that:

\begin{equation} V_{2N}=\{\vec{x} \in \{-1,+1\}^{2N}:\sum_{i=1}^{2N} x_i = 0\} \tag{1} \end{equation}

is the smallest set such that $\mathrm{conv}(V_{2N})=H_{2N}$ where we note that:

\begin{equation} \lvert V_{2N} \rvert= {2N \choose N} \tag{2} \end{equation}

and it's relatively easy to show that:

\begin{equation} \mathrm{conv}(V_{2N}) \subset H_{2N} \tag{3} \end{equation}

So far I haven't managed to show that $\mathrm{conv}(V_{2N}) = H_{2N}$ but I have managed to show that if we define:

\begin{equation} \forall k < N, V_{2k}=\{\vec{x} \in H_{2N}:\sum_{i \in \Gamma} x_i = \sum_{j \notin \Gamma} \lvert x_j \rvert = 0 \land \{x_i\}_{i \in \Gamma} \in \{-1,+1\}^{2k} \} \tag{4} \end{equation}

then we have:

\begin{equation} \forall k < N-1, \mathrm{conv}(V_{2k}) \subset \mathrm{conv}(V_{2k+2}) \tag{5} \end{equation}

I have spent some time thinking about this problem and at this point I'm not sure how to proceed. The challenge is basically to show that $V_{2N}$ is the vertex set of $H_{2N}$.

$\endgroup$
4
  • 2
    $\begingroup$ You should consider the extreme points as, if $C$ is a convex body and $x\in EP(C)$ (its extreme points) $C\setminus \{x\}$ is convex, therefore $EP(C)\subset S$. $\endgroup$ Jul 5, 2019 at 8:34
  • 1
    $\begingroup$ Insight : It seems to me that, if $C$ is intersection of closed half-spaces and bounded, then $S=EP(C)$, but I didn't check this formally. $\endgroup$ Jul 5, 2019 at 9:14
  • $\begingroup$ @DuchampGérardH.E. Thank you for sharing these insights. I suspect that your last point is true and I'm currently thinking about a proof. $\endgroup$ Jul 5, 2019 at 9:56
  • 1
    $\begingroup$ Good Luck ! Do not hesitate to interact anyway. $\endgroup$ Jul 5, 2019 at 10:16

1 Answer 1

5
$\begingroup$

It suffices to verify (see the comment by Duchamp Gérard H. E. and (https://en.wikipedia.org/wiki/Extreme_point)) that the set $V_{2N}$ is precisely the set of extreme points ${\bf EP}(H_{2N})$ of $H_{2N}$. Clearly $V_{2N} \subset {\bf EP}(H_{2N})$. To see the converse, suppose $x \in {\bf EP}(H_{2N})$. Let $\{e_j\}_{j=1}^{2N}$ denote the standard basis vectors in ${\bf R}^{2N}$. If there were two coordinates $1 \le i<j \le 2N$ such that $|x_i|<1$ and $|x_j| <1$, then the representation $$x=\frac{(x+\delta (e_i-e_j))+(x-\delta (e_i-e_j))}{2}$$ for small enough $\delta$, would show that $x$ is not an extreme point of $H_{2N}$. If precisely one index $i \le 2N$ satisfies $|x_i|<1$, then the sum $\sum_{j \le 2N \,: \, j \ne i}x_j$ is $\pm 1$, so $x$ could not be in $H_{2N}$. The only remaining possibility is that $x \in V_{2N}.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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