Understanding convex polytopes (III)

This entry marks the end of my short series of posts regarding convex polytopes and graph-associahedra. I've had lots of fun and learned a lot during this month of research. Here follows a summary of the conclusions of our work.

Understanding the polytope made from $\text{Cycle}_n$ in a constructive manner proved to be harder than anticipated, and we summed up our work in this area with a conjecture relating the $\mathcal{B}$-trees of the cycle on $n+1$ vertices with the lattice paths on the $n \times n$ grid. Recall that the $\mathcal{B}$-trees of the cycle are just binary trees with an extra root at $n+1$, with a certain $\pmod{n+1}$ shift applied to the labels. We can define an equivalence relation based on this operation, and say that two trees $T_1$ and $T_2$ are congruent if they are generated from the same binary tree (with an extra root) $T$. Let $[T]$ denote the equivalence class of $n+1$ trees generated by a canonical binary tree $T$ and the shifting operation. We proceed to define the other side of the relation, lattice paths.

There is a direct construction of lattice paths from $(0,0)$ to $(n,n)$ on the $n \times n$ grid, in particular Dyck paths (those which do not cross the diagonal), from binary trees by expressing a binary tree as a balanced parenthesis sequence. We need to define a parallel of descent for lattice paths, for that is the center of our conjecture. Let $\text{peaks}(P)$ be the number of left-peaks of a lattice path; from the parenthesized construction, a left-peak in the Dyck path is equivalent to a descent in the binary tree. Next, we need to find an operation which serves as parallel for our label shifting on trees. There is a cool operation on Dyck paths (defined by Chen in [1]) which generates a set of $n+1$ lattice paths, and so we define again an equivalence relation based on this operation, with $[P]$ denoting the equivalence class of lattice paths generated from a Dyck path $P$. For distinct $P$ and $P'$, we can show that $[P] \cap [P'] = \varnothing$, and equivalently for our canonical binary trees.

As stated, there is a map $\Phi : \text{binary trees} \rightarrow \text{Dyck paths}$, and we conjecture that the descent generating function of the equivalence class $[T]$ is equal to the descent generating function of the equivalence class $[\Phi(T)]$:

$$\sum_{T' \in [T]} x^{\text{des}(T')} = \sum_{P' \in [\Phi(T)]} x^{\text{peaks}(P')}$$

We verified the conjecture for $n$ up to 13.

On the other hand, we found a combinatorial interpretation for the $\gamma$-polynomial of the cyclohedron. Following the approach of Posntnikov et al. in [2], we defined yet another delicate operation on lattice paths, allowing us to arrive to the desired $\gamma(x) = \sum_{r=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor}\binom{n}{r,r,n-2r} x^r$ in a nice combinatorial way, in contrast to the previous work based on hyper-geometric series manipulations on the $h$-polynomial.

In conclusion, I am extremely happy of the work we've done, considering my very limited exposure to advanced mathematics (and even less to research level mathematics!). I enjoyed the research experience, and the constant unknown factor was such a motivator to keep me going; what's this? What if I do that? Are we doing the right thing? Is there another point of view? I am certainly convinced to pursue mathematics for as long as I can.

References

[1] Chen, Y. M. (2008), The Chung–Feller theorem revisited. Discrete Mathematics, 308(7), 1328-1329.
[2] Postnikov, A., Reiner, V., & Williams, L. (2008). Faces of generalized permutohedra. Doc. Math, 13(207-273), 51.