Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In an excerpt of an article by Bernd Sturmfels, I found:

Theorem 5.5. The tropical Grassmannian $G^{′}_{2,n}$ is a simplical complex known as the space of phylogenetic trees.... It is denoted by $T_n$ and is defined as follows. The vertex set consists of all unordered pairs $\left \{ A,B \right \}$ where $A$ and $B$ are disjoint subsets of $\left [ n \right ]:=\left \{ 1,2, ... , n \right \}$ having cardinality at least two, and $A \cup B=\left [ n \right ]$. Such pairs are called splits. The number of splits is $2^{n−1} − n − 1$. Two splits $\left \{ A,B \right \}$ and $\left \{ A^{'},B^{'} \right \}$ are connected by an edge in the simplicial complex $T_n$ if and only if

(5) $A \sqsubseteq {A}'$ or $A \sqsubseteq {B}'$ or $B \sqsubseteq {A}'$ or $B \sqsubseteq {B}'$.

We define $T_n$ as the largest simplicial complex having this edge graph.... In the language of algebraic combinatorics, $T_n$ is the flag complex of the compatibility graph specified by (5) on the set of all $2^{n−1} − n − 1$ splits.

Example 5.6. ($n = 6$) The two-dimensional simplicial complex $T_6$ has $25$ vertices, $105$ edges and $105$ triangles...

Question: Are $56, 490, 1260, 945$ the "face" numbers for $T_7$?

share|improve this question
"2n-1" above should be "2^{n-1}". Since it would be straightforward to determine the answer to your question using a computer, I'm afraid I don't think this is an appropriate forum for your question. –  Hugh Thomas Oct 2 '11 at 12:56
See also "The Tropical Grassmannian" by David Speyer and Bernd Sturmfels, arxiv.org/abs/math/0304218 . –  Tom Copeland Oct 4 '11 at 13:02
add comment

1 Answer

up vote 5 down vote accepted

You have the right numbers. $\mathrm{Trop} \ G(2,n)$ is the space of phylogenetic trees studied in Billera-Holmes-Vogtman. It has $1 \times 3 \times 5 \times \cdots \times (2n-5)$ maximal faces and $2^{n-1} - n-1$ vertices, matching your $945$ and $56$.

The first several face numbers are $$\begin{matrix} 1 & & & & \\ 1 & 3 & & & \\ 1 & 10 & 15 & & \\ 1 & 25 & 105 & 105 & \\ 1 & 56 & 490 & 1260 & 945 \\ \end{matrix}$$

Write $f(n,k)$ for the number of $k$ faces in $\mathrm{Trop} \ G(2,n)$, we have $$f(n,k) = (k+1) f(n-1,k) + (n+k-2) f(n-1,k-1).$$ I am prone to off by one errors, so check this against the above table.

It is easy to get closed formulas for $f(n,r)$ or $f(n,n-r)$, for small fixed $r$, but there seems to be no simple expression for the middle terms. Billera-Holmes-Vogtman say that there is more discussion in Exercise 5.40 of Enumerative Combinatorics I by Stanley; I don't have my copy with me to check.

share|improve this answer
Thank you for the interesting answer. The exciting thing is that these are preisely the first few entries of oeis.org/A134991 for which there are many closed form expressions and combinatorial interpretations as well as a refinement to a Lagrange inversion formula for e.g.f.s, associated to forests of umbral operator trees and a generator related to permutahedra. Can't get your formula to agree to the above table, though. –  Tom Copeland Oct 2 '11 at 19:41
Rather apparently f(n,k)=(k+1)f(n−1,k)+(n+k+1)f(n−1,k−1) with starting indices n=0 and k=0 –  Tom Copeland Oct 2 '11 at 20:25
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.