2
$\begingroup$

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$?

$\endgroup$
5
  • $\begingroup$ "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. $\endgroup$ Commented Oct 2, 2011 at 12:56
  • $\begingroup$ See also "The Tropical Grassmannian" by David Speyer and Bernd Sturmfels, arxiv.org/abs/math/0304218 . $\endgroup$ Commented Oct 4, 2011 at 13:02
  • $\begingroup$ @Hugh Thomas, given the ease of googling answers to your Q mathoverflow.net/questions/194291/…, on a subject for which you have had conferences, and in light of mathoverflow.net/questions/172955/… (see my comment on the answer already in the OEIS entry) & mathoverflow.net/questions/219449/… (comment on answer in cross-referenced Q), one should refrain from discouraging opinions of the sort above, esp for newbies. $\endgroup$ Commented Feb 26, 2016 at 1:03
  • 1
    $\begingroup$ I am sorry if my comment struck you as overly negative. I am certainly happy that it did not deter you from continuing with MO! Your broader point ("one should refrain from discouraging opinions of the sort above, esp for newbies") is, I think, only half the story. Part of how MO works is by discouraging certain kinds of questions. While this question is not terrible, you have certainly asked other questions that are much more interesting! But I acknowledge that I may not have struck the balance particularly well in this case. $\endgroup$ Commented Mar 13, 2016 at 21:15
  • $\begingroup$ "Interesting" is an incredibly subjective term. If I were to express such opinionated comments here on MO, I would have no time left to make constructive contributions, besides the voting suffices to express that sentiment. Similar comments were made naively for these MO-Qs mathoverflow.net/questions/21929/… and mathoverflow.net/questions/153542/…, revealing the commenters' lack of knowledge of the topic. $\endgroup$ Commented May 12, 2016 at 20:20

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Oct 2, 2011 at 19:41
  • $\begingroup$ 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 $\endgroup$ Commented Oct 2, 2011 at 20:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .