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$

1 Answer 1

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$ Commented Dec 17, 2014 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.
    Commented Dec 17, 2014 at 9:18
  • $\begingroup$ Although there is no complete solution here, I'm giving it the green tick for being very useful. $\endgroup$ Commented Sep 12, 2017 at 5:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .