0
$\begingroup$

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. enter image description here

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$.

Related question:https://math.stackexchange.com/questions/522950/counts-of-simplex-faces-of-the-cqhrl-d-polytope-family

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

Vertices of CQHRLd chart

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}$$

$\endgroup$

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.