"The Dream of a Ridiculous Man"

And yet it's so simple: in one day, in one hour - it could all be set up at once! The main thing is -- love others as yourself, that's the main thing, and it's everything, there's no need for anything else at all: it will immediately be discovered how to set things up. And yet this is merely an old truth, repeated and read a billion times, but still it has never taken root! "The consciousness of life is higher than life, the knowledge of the laws of happiness is higher than happiness" -- that is what must be fought! And I will. If only everyone wants it, everything can be set up at once.
And I found that little girl . . . And I'll go! I'll go!

-- The Dream of a Ridiculous Man, F.M. Dostoyevski

I have been working on some book typesetting, and a few things are almost ready to be shared. This is not one of them though; at least not the English translation.

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.