7
$\begingroup$

Let $2\le k\le n-1$ and define the polytope $$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n : -1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$ There are $\binom nk$ constraints: the sum of any $k$ variables is in $[-1,1]$. Surely this is known, but I didn't manage to find it.

Does this polytope have a name? What is known about it? Changing the lower bound from $-1$ to 0 is just a scale+translate so that would do instead.

This problem arose in a graph reconstruction study but isn't needed for that any more.

$\endgroup$
4
$\begingroup$

After computing the vertices, I've reorganized this answer into four sections: Facts / Definitions, Conjectures / Observed Patterns, Polymake Computations, and the Table of Volumes

Some Facts and Definitions:

First, note that the defining inequalities of $P_k(n)$ and $P_{n-k}(n)$ can be related by an invertible linear transformation, so they are (combinatorially) isomorphic. In particular, $P_{n-1}(n)$ is isomorphic to $P_1(n)$, which is of course just an $n$-cube.

Here's a hopefully not too headache-inducing animation of $P_2(3)$:

p23

Next, I define the polytopes $\mathfrak{A}^n$, from E.P. Baranovskii, "Partitioning of Euclidean space into L-polytopes" in the volume "Discrete Geometry and Topology", Proceedings of the Steklov Institute of Mathematics, vol. 196.

The $n$-polytope $\mathfrak{A}^n$ is defined as the convex hull on the following $2n+2$ points: the vertices of a regular $n$-simplex $\Delta^n$ centered at the origin and the vertices of the inversion of $\Delta^n$ through the origin.

Now recall that a point is a vertex of an $n$-polytope $P$ if and only if it is the unique solution of (at least) $n$ of the defining hyperplanes of $P$ and lies within $P$. $P_k(n)$ is symmetric under inversion through the origin as well as all permutations of the $n$ coordinates. From these two facts, we can prove that $P_k(n)$ always has the following four families of points as vertices:

1) The point $\left(\frac{1}{k},\dots,\frac{1}{k}\right)$; note that it lies at the intersection of the $\binom{n}{k}\geq n$ hyperplanes defined by $\sum_{i=1}^kx_{j_i}=1$ (with the same choice of sign, and over all choices $1\leq j_1\leq\cdots\leq j_k\leq n$).

2) Similarly, its inversion through the origin $\left(-\frac{1}{k},\dots,-\frac{1}{k}\right)$ is also a vertex.

3) The point $\left(\frac{2k-1}{k},-\frac{1}{k},\dots,-\frac{1}{k}\right)$ and the points whose coordinates are permutations of this one ($n$ points in total). This point lies at the intersection of $\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n}{k}$ hyperplanes defined by $x_1+\sum_{i=1}^{k-1}x_{j_i}=1$ and $\sum_{i=1}^kx_{l_i}=-1$ (over all choices $2\leq j_1\leq\cdots\leq j_{k-1}\leq n$ and $2\leq l_1\leq\cdots\leq l_{k}\leq n$).

4) The inversions of the previously defined points through the origin: $\left(-\frac{2k-1}{k},\frac{1}{k},\dots,\frac{1}{k}\right)$ and permutations.

These will be called the four basic families of vertices.

Finally, it will be useful to introduce the following notation:

$\{x\}^n$ denotes the point $\left(x,\dots,x\right)$.

$\{x\}^j\{y\}^{n-j}$ denotes the orbit of the point $\left(x,\dots,x,y,\dots,y\right)$ (where the first $j$ coordinates are equal to $x$ and the last $n-j$ coordinates are equal to $y$) under the permutation of all $n$ coordinates.

The number of points in $\{x\}^j\{y\}^{n-j}$ is $\binom{n}{j}$, and the above results show that $\{1/k\}^n$, $\{1/k\}^{n-1}\{-\frac{2k-1}{k}\}^1$, $\{\frac{2k-1}{k}\}^1\{-1/k\}^{n-1}$, and $\{-1/k\}^n$ are always vertices of $P_k(n)$.

Conjectures / Patterns observed in the computations below

1) Besides the four basic families of points, the vertices of $P_k(n)$ always take the form $\{x_j\}^j\{y_j\}^{n-j}$ with $x_j>0$ and $y_j<0$, and there is only one such pattern for each distinct value of $j$.

Is there a nice formula for $x_j$ and $y_j$ (depending on $j$,$k$, and $n$)? The vertex data below exhibits various patterns: e.g. for $k=2$, $x_j=1/2$ and $y_j=-1/2$ except when $j=1,n-1$.

Now let's define the spectrum of $P_k(n)$ to be the values of $j$ such that it has vertices of the above form.

If the above conjecture about the form of the vertices is true, then the spectrum of the $n$-cube $P_{n-1}(n)$ must include all $0\leq j\leq n$ (to get the required $2^n$ vertices).

Note that by the central symmetry of $P_k(n)$, if the spectrum includes $j$, it also includes $n-j$. The spectra of $P_k(n)$ and $P_{n-k}(n)$ seem to be identical in the computations below, but I haven't checked that the linear transformation between them transforms the $\{x_j\}^j\{y_j\}^{n-j}$ nicely.

I have shown above that $0,1,n-1,n$ are always present in the spectrum. One can show that $2$ (and hence also $n-2$) is never present in the spectrum of $P_2(n)$ (I won't write the proof here, but in short it comes down to seeing that one cannot get $n$ linearly independent hyperplanes corresponding to a vertex of that form). It seems from the computations below that those are the only values excluded from the spectrum of $P_2(n)$, but I don't know how to prove this.

Showing that other values are excluded or included in the spectra of various $P_k(n)$ seems to require some tricky and intricate arguments about the linearly independent sets of the $2\binom{n}{k}$ bounding hyperplanes.

2) The vertices of $P_m(2m)$, $P_{m}(2m+1)$ and $P_{m+1}(2m+1)$ consist of only the four basic families. In other words, the spectrum of $P_m(2m)$ is $2m,2m-1,1,0$, and the spectra of $P_m(2m+1)$ and $P_{m+1}(2m+1)$ are $2m+1,2m,1,0$.

Furthermore, $P_{m}(2m+1)$ (and thus $P_{m+1}(2m+1)$) is isomorphic to $\mathfrak{A}^{2m+1}$, while the f-vector of $P_m(2m)$ agrees with that of $\mathfrak{A}^{2m}$ up to the $(m-1)$th component.

3) The number of $(n-1)$-faces of $P_k(n)$ is precisely $2\binom{n}{k}$; none of the defining inequalities are redundant. (I thought I had a proof of this before but I think it wasn't right).

4) The volumes of $P_2(n)$ are all equal to 4.

Computations in polymake for $3\leq n\leq 9$

The polymake files I generated are here (34 MB ZIP). The files Pnk.poly correspond to $P_k(n)$ (note the ordering of the numbers is switched), and the files An.poly correspond to $\mathfrak{A}^n$.

$n=3$

$P_2(3)$:

Vertices: $\{1/2\}^3$, $\{1/2\}^2\{-3/2\}^1$, $\{3/2\}^1\{-1/2\}^2$, $\{-1/2\}^3$

Spectrum: 3,2,1,0

f-vector: [8 12 6]

Isomorphic to $\mathfrak{A}^3$, which is also the 3-cube (as is clear in the above animation).


$n=4$

$P_2(4)$:

Vertices: $\{1/2\}^4$, $\{1/2\}^3\{-3/2\}^1$, $\{3/2\}^1\{-1/2\}^3$, $\{-1/2\}^4$

Spectrum: 4,3,1,0

f-vector: [10 28 30 12]

Isomorphic to the bipyramid over the 3-cube (which I found from finding the f-vector on this page on permutation polytopes). Compare the f-vector of $\mathfrak{A}^4$: [10 40 60 30]

$P_3(4)$:

Vertices: $\{1/3\}^4$, $\{1/3\}^3\{-5/3\}^1$, $\{1\}^2\{-1\}^2$, $\{5/3\}^1\{-1/3\}^3$, $\{-1/3\}^4$

Spectrum: 4,3,2,1,0

f-vector: [16 32 24 8]

Isomorphic to the 4-cube.


$n=5$

$P_2(5)$ and $P_3(5)$

Vertices of $P_2(5)$: $\{1/2\}^5$, $\{1/2\}^4\{-3/2\}^1$, $\{3/2\}^1\{-1/2\}^4$, $\{-1/2\}^5$

Vertices of $P_3(5)$: $\{1/3\}^5$, $\{1/3\}^4\{-5/3\}^1$, $\{5/3\}^1\{-1/3\}^4$, $\{-1/3\}^5$

Spectrum: 5,4,1,0

f-vector: [12 60 120 90 20]

Isomorphic to $\mathfrak{A}^5$.

$P_4(5)$:

Vertices: $\{1/4\}^5$, $\{1/4\}^4\{-7/4\}^1$, $\{3/4\}^3\{-5/4\}^2$, $\{5/4\}^2\{-3/4\}^3$, $\{7/4\}^1\{-1/4\}^4$, $\{-1/4\}^5$

Spectrum: 5,4,3,2,1,0

f-vector: [32 80 80 40 10]

Isomorphic to the 5-cube.


$n=6$

$P_2(6)$ and $P_4(6)$

Vertices of $P_2(6)$: $\{1/2\}^6$, $\{1/2\}^5\{-3/2\}^1$, $\{1/2\}^3\{-1/2\}^3$, $\{3/2\}^1\{-1/2\}^5$, $\{-1/2\}^6$

Vertices of $P_4(6)$: $\{1/4\}^6$, $\{1/4\}^5\{-7/4\}^1$, $\{1/2\}^3\{-1/2\}^3$, $\{7/4\}^1\{-1/4\}^5$, $\{-1/4\}^6$

Spectrum: 6,5,3,1,0

f-vector: [34 204 510 520 210 30]

(c.f. f-vector of bipyramid over the 5-cube: [34 144 240 200 90 20])

$P_3(6)$

Vertices: $\{1/3\}^6$, $\{1/3\}^5\{-5/3\}^1$, $\{5/3\}^1\{-1/3\}^5$, $\{-1/3\}^6$

Spectrum: 6,5,1,0

f-vector: [14 84 240 330 200 40]

(c.f. f-vector of $\mathfrak{A}^6$: [14 84 280 490 420 140])

$P_5(6)$

Vertices: $\{1/5\}^6$, $\{1/5\}^5\{-9/5\}^1$, $\{3/5\}^4\{-7/5\}^2$, $\{1\}^3\{-1\}^3$, $\{7/5\}^2\{-3/5\}^4$, $\{9/5\}^1\{-1/5\}^5$, $\{-1/5\}^6$

Spectrum: 6,5,4,3,2,1,0

f-vector: [64 192 240 160 60 12]

Isomorphic to the 6-cube.


$n=7$

$P_2(7)$ and $P_5(7)$

Vertices of $P_2(7)$: $\{1/2\}^7$, $\{1/2\}^6\{-3/2\}^1$, $\{1/2\}^4\{-1/2\}^3$, $\{1/2\}^3\{-1/2\}^4$, $\{3/2\}^1\{-1/2\}^6$, $\{-1/2\}^7$

Vertices of $P_5(7)$: $\{1/5\}^7$, $\{1/5\}^6\{-9/5\}^1$, $\{1/3\}^4\{-1/3\}^3$, $\{1/3\}^3\{-1/3\}^4$, $\{9/5\}^1\{-1/5\}^6$, $\{-1/5\}^7$

Spectrum: 7,6,4,3,1,0

f-vector: [86 742 2226 2800 1610 420 42]

$P_3(7)$ and $P_4(7)$

Vertices of $P_3(7)$: $\{1/3\}^7$, $\{1/3\}^6\{-5/3\}^1$, $\{5/3\}^1\{-1/3\}^6$, $\{-1/3\}^7$

Vertices of $P_4(7)$: $\{1/4\}^7$, $\{1/4\}^6\{-7/4\}^1$, $\{7/4\}^1\{-1/4\}^6$, $\{-1/4\}^7$

Spectrum: 7,6,1,0

f-vector: [16 112 448 980 1120 560 70]

Isomorphic to $\mathfrak{A}^7$.

$P_6(7)$

Vertices: $\{1/6\}^7$, $\{1/6\}^6\{-11/6\}^1$, $\{1/2\}^5\{-3/2\}^2$, $\{5/6\}^4\{-7/6\}^3$, $\{7/6\}^3\{-5/6\}^4$, $\{3/2\}^2\{-1/2\}^5$, $\{11/6\}^1\{-1/6\}^6$, $\{-1/6\}^7$

Spectrum: 7,6,5,4,3,2,1,0

f-vector: [128 448 672 560 280 84 14]

Isomorphic to the 7-cube.


$n=8$

$P_2(8)$ and $P_6(8)$

Vertices of $P_2(8)$: $\{1/2\}^8$, $\{1/2\}^7\{-3/2\}^1$, $\{1/2\}^5\{-1/2\}^3$, $\{1/2\}^4\{-1/2\}^4$, $\{1/2\}^3\{-1/2\}^5$, $\{3/2\}^1\{-1/2\}^7$, $\{-1/2\}^8$

Vertices of $P_6(8)$: $\{1/6\}^8$, $\{1/6\}^7\{-11/6\}^1$, $\{1/3\}^5\{-2/3\}^3$, $\{1/2\}^4\{-1/2\}^4$, $\{1/3\}^3\{-2/3\}^5$, $\{11/6\}^1\{-1/6\}^7$, $\{-1/6\}^8$

Spectrum: 8,7,5,4,3,1,0

f-vector: [200 2160 8120 13048 10220 4032 756 56]

$P_3(8)$ and $P_5(8)$

Vertices of $P_3(8)$: $\{1/3\}^8$, $\{1/3\}^7\{-5/3\}^1$, $\{1/3\}^4\{-1/3\}^4$, $\{5/3\}^1\{-1/3\}^7$, $\{-1/3\}^8$

Vertices of $P_5(8)$: $\{1/5\}^8$, $\{1/5\}^7\{-9/5\}^1$, $\{1/3\}^4\{-1/3\}^4$, $\{9/5\}^1\{-1/5\}^7$, $\{-1/5\}^8$

Spectrum: 8,7,4,1,0

f-vector: [88 704 2632 5684 7420 5040 1400 112]

$P_4(8)$

Vertices: $\{1/4\}^8$, $\{1/4\}^7\{-7/4\}^1$, $\{7/4\}^1\{-1/4\}^7$, $\{-1/4\}^8$

Spectrum: 8,7,1,0

f-vector: [18 144 672 1876 3080 2800 1190 140]

(c.f. $\mathfrak{A}^8$: [18 144 672 2016 3780 4200 2520 630])

$P_8(7)$

Vertices: $\{1/7\}^8$, $\{1/7\}^7\{-13/7\}^1$, $\{3/7\}^6\{-11/7\}^2$, $\{5/7\}^5\{-9/7\}^3$, $\{1\}^4\{-1\}^4$, $\{9/7\}^3\{-5/7\}^5$, $\{11/7\}^2\{-3/7\}^6$, $\{13/7\}^1\{-1/7\}^7$, $\{-1/7\}^8$

Spectrum: 8,7,6,5,4,3,2,1,0

f-vector: [256 1024 1792 1792 1120 448 112 16]

Isomorphic to the 8-cube.


$n=9$

$P_2(9)$ and $P_7(9)$

Vertices of $P_2(9)$: $\{1/2\}^9$, $\{1/2\}^8\{-3/2\}^1$, $\{1/2\}^6\{-1/2\}^3$, $\{1/2\}^5\{-1/2\}^4$, $\{1/2\}^4\{-1/2\}^5$, $\{1/2\}^3\{-1/2\}^6$, $\{3/2\}^1\{-1/2\}^8$, $\{-1/2\}^9$

Vertices of $P_7(9)$: $\{1/7\}^9$, $\{1/7\}^8\{-13/7\}^1$, $\{2/7\}^6\{-5/7\}^3$, $\{3/7\}^5\{-4/7\}^4$, $\{4/7\}^4\{-3/7\}^5$, $\{5/7\}^3\{-2/7\}^6$, $\{13/7\}^1\{-1/7\}^8$, $\{-1/7\}^9$

Spectrum: 9,8,6,5,4,3,1,0

f-vector: [440 5598 24912 49728 51660 29232 8736 1260 72]

$P_3(9)$ and $P_6(9)$

Vertices of $P_3(9)$: $\{1/3\}^9$, $\{1/3\}^8\{-5/3\}^1$, $\{1/3\}^5\{-1/3\}^4$, $\{1/3\}^4\{-1/3\}^5$, $\{5/3\}^1\{-1/3\}^8$, $\{-1/3\}^9$

Vertices of $P_6(9)$: $\{1/6\}^9$, $\{1/6\}^8\{-11/6\}^1$, $\{5/18\}^5\{-7/18\}^4$, $\{7/18\}^4\{-5/18\}^5$, $\{11/6\}^1\{-1/6\}^8$, $\{-1/6\}^9$

Spectrum: 9,8,5,4,1,0

f-vector: [272 3078 15072 39228 58212 46872 18648 3192 168]

$P_4(9)$ and $P_5(9)$

Vertices of $P_4(9)$: $\{1/4\}^9$, $\{1/4\}^8\{-7/4\}^1$, $\{7/4\}^8\{-1/4\}^1$, $\{-1/4\}^9$

Vertices of $P_5(9)$: $\{1/5\}^9$, $\{1/5\}^8\{-9/5\}^1$, $\{9/5\}^8\{-1/5\}^1$, $\{-1/5\}^9$

Spectrum: 9,8,1,0

f-vector: [20 180 960 3360 7560 10500 8400 3150 252]

Isomorphic to $\mathfrak{A}^9$.

$P_8(9)$

Vertices: $\{1/8\}^9$, $\{1/8\}^8\{-15/8\}^1$, $\{3/8\}^7\{-13/8\}^2$, $\{5/8\}^6\{-11/8\}^3$, $\{7/8\}^5\{-9/8\}^4$, $\{9/8\}^4\{-7/8\}^5$, $\{11/8\}^3\{-5/8\}^6$, $\{13/8\}^2\{-3/8\}^7$, $\{15/8\}^1\{-1/8\}^8$, $\{-1/8\}^9$

Spectrum: 9,8,7,6,5,4,3,2,1,0

f-vector: [512 2304 4608 5376 4032 2016 672 144 18]

Isomorphic to the 9-cube.

Table of volumes

+-----+---+---------+-----+--------+--------+-------+----+
| n\k | 2 | 3       | 4   | 5      | 6      | 7     | 8  |
+-----+---+---------+-----+--------+--------+-------+----+
| 3   | 4 |         |     |        |        |       |    |
+-----+---+---------+-----+--------+--------+-------+----+
| 4   | 4 | 16/3    |     |        |        |       |    |
+-----+---+---------+-----+--------+--------+-------+----+
| 5   | 4 | 8/3     | 8   |        |        |       |    |
+-----+---+---------+-----+--------+--------+-------+----+
| 6   | 4 | 16/9    | 2   | 64/5   |        |       |    |
+-----+---+---------+-----+--------+--------+-------+----+
| 7   | 4 | 32/27   | 8/9 | 8/5    | 64/3   |       |    |
+-----+---+---------+-----+--------+--------+-------+----+
| 8   | 4 | 64/81   | 4/9 | 64/135 | 4/3    | 256/7 |    |
+-----+---+---------+-----+--------+--------+-------+----+
| 9   | 4 | 128/243 | 2/9 | 8/45   | 64/243 | 8/7   | 64 |
+-----+---+---------+-----+--------+--------+-------+----+
$\endgroup$
3
  • $\begingroup$ All this is very interesting, thanks! Do you have a conjecture (or proof!) about what the vertices are? $\endgroup$ Dec 17 '14 at 7:41
  • $\begingroup$ Good question. I hadn't looked too carefully at them yet, but there are definitely some obvious patterns (e.g. in the families $P_2(n)$ and ($P_m(2m+1)$ & $P_{m+1}(2m+1)$)). I will try to update later this week. $\endgroup$
    – j.c.
    Dec 17 '14 at 9:18
  • $\begingroup$ Although there is no complete solution here, I'm giving it the green tick for being very useful. $\endgroup$ Sep 12 '17 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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