Counts of certain types of faces of the $CQHRL_d$ polytope family

This is essentially a counting question, with motivation being supplied by a particular polytope family called crenellated quad hyper-rope loops of dimension $d$ ($CQHRL_d$) ($d$ $\ge$ $5$) and certain faces of them. In particular, the question can be answered just by reference to the progression of diagrams (the first few shown below) which suffice to provide a framework for the face lattices of this polytope family.

The above diagrams show all the vertices, some of the edges, and all $d$ of the quadrilateral 2-faces (labeled $Q0$, $Q1$, …) as a representation of $CQHRL_d$ for $d$ = $5$ to $8$. Additionally:

$\bullet$ All pairs of vertices not on the same quadrilateral subtend an edge.

$\bullet$ Vertices shown as distinct but having the same number label are the same vertex (i.e., along the upper and lower and lower edges of the diagram, and also vertex $0$).

$\bullet$ The diagrams can be thought of as forming a loop, with $Q0$ sharing vertex $0$ with $Q(d – 1)$, including a Möbius twist for odd $d$.

$\bullet$ No proper face contains two consecutively numbered quadrilaterals (mod $d$).

$\bullet$ Any pair of quadrilaterals that are two apart (mod $d$) have a vertex of intersection, and form a 4-dimensional face.

$\bullet$ Any pair of quadrilaterals that are at least three apart (mod $d$) are disjoint, and form a 5-dimensional face which is the free join of two quadrilaterals.

$\bullet$ For $q$ > $0$, $q$ disjoint quadrilaterals form a face of dimension $3q – 1$; a free join of quadrilaterals.

$\bullet$ If $d$ > $3q$, it is possible to take a pyramid over such a face (forming another face) by adding a vertex which is not diagonally across a quadrilateral from one of the vertices of the $q$ quadrilaterals.

Finally, the question follows. (Thank you for your patience.)

Given dimension $d$, number of disjoint quads $q$, and number of pyramid apices $v$, how many faces of $CQHRL_d$ which are v-fold pyramids over a free join of $q$ quadrilaterals are there, where one of the quadrilaterals is $Q0$?

This combinatorial function is a useful building block in counting certain types of faces of $CQHRL_d$.

• By the way, if anyone knows how to write CQHRL as a subscript in MathJax, your help is appreciated. Oct 10 '13 at 19:44
• <sub></sub> worked for this. Nov 5 '13 at 16:22

The vertices of $CQHRL_d$ are shown above in a matrix format, such that vertices diagonally across a quad face from each other are in the same column or in the same row. (Such vertex pairs are the only ones that do not subtend an edge of $CQHRL_d$.) The vertices of $Q0$ are shown in red, and are contained in rows 1 - 3, and in columns 1 - 3 of the matrix diagram.

We will begin by counting the v-fold pyramids over $Q0$ which are faces of $CQHRL_d$. The vertices eligible to be apices of the v-fold pyramid are those not appearing in rows $1 - 3$, and not in columns $1 - 3$. This set of vertices lies in a zig-zag line beginning with $-3$, and preceding to $3$, $4$, ... (-1)d-1(d - 2), (-1)d-1(d - 1) lying in rows $4$ through $d$, and in columns $4$ through $d$, beginning and ending on the main diagonal and also containing vertices on the subdiagonal; containing $2(d - 3) - 1$ = $2d - 7$ vertices. We want to choose $v$ vertices from this zig-zag line such that no two of them are in the same row nor the same column. The just-stated condition is equivalent to having no two of the $v$ vertices next to each other on the straightened-out zig-zag line. As explained by this MSE Q&A, we can choose $v$ vertices meeting the condition in ${2d - 6 - v \choose v}$ ways; hence there are ${2d - 6 - v \choose v}$ v-fold pyramids over $Q0$ which are faces of $CQHRL_d$. (Clearly, $v$ cannot exceed $d - 3$.) Such faces have dimension $2 + v$.

Now, suppose we are beginning with a free join of $q$ quadrilaterals, one of which is $Q0$. Each quadrilateral has vertices that lie in disjoint sets of three consecutive row/columns (i.e., the row numbers taken up are the same as the column numbers). Thus, you must have $d$ $\geq$ $3q$. If $d$ = $3q$, there is exactly one such face (the free join of $Q0$, $Q3$, ...$Q3q-3$), having dimension $3q - 1$ = $d - 1$ (hence a facet). For $v$ $\leq$ $d - 3q$, how many v-fold pyramids can be formed over a free join of $q$ quads (including $Q0$)?

We observe that there are $q$ gaps (between each quad) whose length we represent by the number of row/columns taken up by the gap - including the case of a zero-length gap. We will number the gaps from $0$ to $q - 1$. We'll plan to sum the contributions of each combination of:

• arrangement of gaps, which correspond to the ordered partitions of $d - 3q$ with $q$ addends(admitting zero addends); and
• counts of vertices within each gap which sum to $v$; the requisite total of apices.

We denote the gap lengths $g_i$, and the number of vertices in each gap $v_i$. We have:

$g_i$, $v_i$ $\geq$ $0$

$\sum_{i=0}^{q-1} g_i$ = $d - 3q$

$\sum_{i=0}^{q-1} v_i$ = $v$

The potential possibilities for $v_i$ (in the $i$th gap) are from $0$ to $g_i$, with the count of arrangements of $v_i$ vertices ${2g_i - v_i \choose v_i}$. Using the counting principle, we conclude that the contribution from each combination of gap arrangements & vertices therein is $\prod_{i=0}^{q-1} {2g_i - v_i \choose v_i}$.

Note that it follows necessarily that the two arguments of each multiplicand choose function have the same even-odd parity; if $v_i$ is odd, so is $2g_i - v_i$, and if $v_i$ is even, so is $2g_i - v_i$. Also, note that the sum of the top arguments of the choose functions in the product is $2d - 6q - v$. We now show that the matching even-odd parity of the arguments in each multiplicand choose function is a sufficient condition for the product to represent a gap arrangement/vertices therein combination.

Say you are given $n_i$, $v_i$ $\geq$ $0$, $n_i$ $\geq$ $v_i$ and $n_i$ $\equiv$ $v_i$ (mod $2$), for $i$ = $0$ to $q-1$, where

$\sum_{i=0}^{q-1} n_i$ = $2d - 6q - v$

$\sum_{i=0}^{q-1} v_i$ = $v$

Setting $g_i$ = $\frac{n_i + v_i}{2}$, we verify that the given set of choose function arguments corresponds to the $g_i$ / $v_i$ gap arrangement/vertices combination. We conclude that (with the $n_i$ and $v_i$ sums given above) the count of v-fold pyramids over all possible free joins of q quads (including $Q0$) is $$\sum_{∀i, v_i \equiv n_i (mod 2)} \left[\prod_{i=0}^{q-1} {n_i \choose v_i}\right]$$

Now, we'll directly apply this result (setting the variable from the other question on the left, from this question on the right):

$n$ = $2d - 6q - v$

$m$ = $v$

$k$ = $q - 1$

Simplifying, the count of v-fold pyramids over all possible free joins of $q$ quads (including $Q0$) is $${2d - 5q - v - 1 \choose v} {d - 2q - 1 \choose q - 1}$$