An inequality about embedding of cube into metric spaces

Question

A k-cube in $X$ is a function $\psi:\{-1,1\}^k\to (X,d)$.

An edge of a cube is a pair of points $\{\psi(\epsilon_1),\psi(\epsilon_2)\}$ in $X$ such that $\epsilon_1$ and $\epsilon_2 $ differ in exactly 1 coordinate. Denote the set of all edges by $E$.

An diagonal of a cube is a pair of points $\{\psi(\epsilon_1),\psi(\epsilon_2)\}$ in $X$ such that $\epsilon_1=-\epsilon_2 $ . Denote the set of all diagonal by $D$.

For any fixed $\epsilon\in\{-1,1\}^k$, denote $E_{\epsilon}$ the set of edges from $\epsilon$ to $-\epsilon$ obtained by changing the the coordinates sucessively, e.g. $E_{(1,-1,1)}=\{ \{(1,-1,1),(-1,-1,1)\},\{(-1,-1,1),(-1,1,1)\},\{(-1,1,1),(-1,1,-1)\} \}$. It is clear that $|E_{\epsilon}|=k$. By triangle inequality and Cauchy-Schwarz we have

$$ k\sum_{E_{\epsilon}} \text{edge}^2 \ge \text{diag}^2(\epsilon) $$

Summing over all $\epsilon$ gives

$$ k\sum_{E} \text{edge}^2 \ge \sum_D\text{diag}^2. $$

Now, assume that there is a (very small) $\theta\in(0,1)$ such that

$$ k\sum_{E} \text{edge}^2 \ge \sum_D\text{diag}^2 \ge k(1-\theta)^2\sum_{E} \text{edge}^2, $$

we can find $\epsilon_0$ satisfying

$$ k\sum_{E_{\epsilon_0}} \text{edge}^2 \ge \text{diag}^2(\epsilon_0) \ge 2^{-k+1}k(1-\theta)^2\sum_{E} \text{edge}^2. $$

It is claimed that, under the assumption, we have $$ \text{diag}^2(\epsilon_0)\ge k\left[(1-\theta)^2 \sum_E\text{edge}^2 - \sum_{E\backslash E_{\epsilon_0}}\text{edge}^2 \right]. $$ Why is it so?

This might be very easy but I really can't think of a way. This inequality is used in the proof of Bourgain-Milman-Wolfson that we can always embed an arbitrary large Hamming cube into a metric space with no non-trivial metric type.

I don't know if this is relevant or not, but $\theta=\frac {\delta^2}{k^22^{k+12}}$ some $\delta\in (0,1)$.

Answer 1

By now surely you already know the answer, but here it is anyway. It follows from the assumption on $\theta$ that $$ \text{diag}^2(\epsilon_0)\ge k(1-\theta)^2 \sum_E\text{edge}^2 - \sum_{D_0} \text{diag}^2 $$ where $D_0$ is the set of diagonals excluding the one determined by $\epsilon_0$. We already know that for every $\epsilon$ we have $$ k\sum_{E_{\epsilon}} \text{edge}^2 \ge \text{diag}^2(\epsilon), $$ so adding up over all the diagonals except the one determined by $\epsilon_0$, we have $$ k \sum_{E\backslash E_{\epsilon_0}}\text{edge}^2 \ge \sum_{D_0} \text{diag}^2 $$ and the desired inequality follows immediately.

The key here is the remark right after equation (2.1.2) in the Bourgain-Milman-Wolfson paper: "the edges, belonging to identity paths of different diagonals, are all distinct".