1

In an extract 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 {A,B} where A and B are disjoint
subsets of [n] := {1, 2, . . . , n} having cardinality at least two, and A ∪ B = [n].
Such pairs are called splits. The number of splits is 2^(n−1) − n − 1. Two splits {A,B} and
{A′,B′} are connected by an edge in the simplicial complex Tn if and only if
(5) A ⊆ A′ or A ⊆ B′ or B ⊆ A′ or B ⊆ 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?

flag
"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 at 12:56
See also "The Tropical Grassmannian" by David Speyer and Bernd Sturmfels, arxiv.org/abs/math/0304218 . – Tom Copeland Oct 4 at 13:02

1 Answer

5

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.

link|flag
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 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 at 20:25

Your Answer

Get an OpenID
or

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