Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)

Question

Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating polynomial $g(t) = \sum_k g_k tˆk$.

Question 1: What is known about $g(t)$ ?

Consider $n$ to be quite large.

Question 2: Is it true that coefficients $g_k$ are well approximated by the Gaussian ? (It might be natural to expect such phenomena for any symmetric polytopes).

See also: What are compact manifolds such that GROWTH (of spheres volumes) is well approximated by the Gaussian normal distribution?

More on graphs <-> polytopes correspondence examples in beautiful post in Gil Kalai's blog: https://gilkalai.wordpress.com/2009/02/28/ziegler%C2%B4s-lecture-on-the-associahedron/ See also: What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?

Answer 1

Let's consider the associahedron whose vertices are triangulations of an $n$-gon. Sleator, Tarjan, and Thurston (Rotation distance, triangulations, and hyperbolic geometry, JAMS, 1988) give a simple argument that the maximum distance between two triangulations is at most $2n-10$. Namely, if you pick a boundary vertex $v$, it's always possible to do a flip which increases its degree, unless you are already at the triangulation which has all its diagonals incident to $v$. So, if $T$ and $T'$ are two triangulations, you can get from $T$ to $T'$ via the triangulation with all diagonals incident to $v$ in at most $2n-6 - \textrm{deg}_T(v) - \textrm{deg}_{T'}(v)$ steps, where the degrees are with respect to the diagonals only. They then give a simple averaging argument that if $n$ is at least 12, $v$ can be chosen so the sum of the degrees of $v$ in $T$ and $T'$ is at least 4.

If we construct the generating polynomial starting from the bottom of the Tamari lattice, $T_0$, (where all the edges are incident to vertex $0$) as suggested by Sam, the maximum distance will be much less: by the same argument, we can always increase the degree of 0 by one at each step, and obviously we can't increase it by more than one. So the distance of $T$ from $T_0$ is just $n-3-\deg_T(0)$.

The count of triangulations by degree of a fixed vertex is known to be given by ballot numbers. (See A009766 of the OEIS.) The formula for those at distance $k$ is $\frac{n-2-k}{n-2}\binom{n-3+k}{n-3}$. This is very far from being approximately Gaussian.

If we start from a more typical vertex of the associahedron, though, the results might look more like what the OP proposed.

Edited to add: Sleator, Tarjan, and Thurston actually showed (using hyperbolic geometry) that for $n$ sufficiently large, the bound they found is tight. Their proof gave no indication of how big $n$ had to be, and for small values of $n$ (but at least 12), their bound was computed to be sharp. Finally their bound was shown to be sharp for all $n$ at least 12 by Pournin, https://arxiv.org/abs/1207.6296. This shows that there are some vertices of the associahedron for which the behaviour will be quite different from the one I discussed above.