## ‘Shear’ convex polyhedra

I came up with what seems quite a beautiful geometric construction solving the problem described below. On a compact convex set  $C \subset \mathbb{R}^n$  consider the function

$\displaystyle w_1(x) = \max_{y \in C}\, y_1 - \min_{y \in C}\, y_1$

$\displaystyle\text{s.t.}\,\,\,\, y_2=x_2,\, ...,\, y_n = x_n.$

where we denote $x = (x_1,\, ...,\, x_n).$  In other words, “hanging” in the point  $x,$  we measure the “width” of the set along the first axis of the Cartesian system (note that  $w_1(x)$  actually doesn’t depend on $x_1$). In the same fashion we define functions  $w_2(x),\, ...,\, w_n(x)$  ($w_i(x)$ measures the “width” along the $i$-th axis). Now consider the following functionals of  $C$:

$\displaystyle w^*(C) = \max_{x \in C} \left[\sum_{i=1}^n w_i(x)\right];$

$\displaystyle w_i^*(C) = \max_{x \in C}\, w_i(x);$

$\displaystyle W^*(C) = \sum_{i=1}^n w_i^*(C).$

Namely,  $w^*$  is the maximum sum of “widths”, whereas  $W^*$  is the sum of maximum “widths”, hence  $w^* \le W^*.$  Moreover,  $w^* = W^*$  for some archetypal examples of convex polyhedra: hyperrectangle (box) and rectangular simplex, and it is easy to begin thinking that we have equality for any convex polyhedra. To give a partial justification for this intuition (which is though incorrect in general), consider rectangular convex polyhedra: to build such a polyhedron in  $\mathbb{R}^n,$  we fix a pair of points  $(x_i, y_i)$  on each coordinate axis $i,$ and then take the convex hull of these  $2n$  points. We can easily prove the following geometric fact about such polyhedra:

Lemma

For any rectangular (in the sense defined above) convex polyhedron in  $\mathbb{R}^2,$ that is, rectangular convex quadrilateral, it holds  $w^* = W^*.$

However already in  $n = 3$  one may find a convex polyhedron (in fact a rectangular one), such that  $w^* < W^*.$

Problem

Point out a sequence  $\{P_n\}$,  $P_n \in \mathbb{R}^n$,  of  [‘shear’]  convex polyhedra, for which

$\displaystyle W^*(P_n) = \Theta(n), \quad \text{but} \quad w^*(P_n) = O(1).$

Later on I will describe the solution to this problem.