8
$\begingroup$

Updated: My first post had a mistake because I confused in my mind two different but related sets. Hopefully the description below is correct now.

Let $\Lambda$ be a finite set. Let $\Lambda^{(2)}$ be the set of unordered pairs $\{x,y\}\subset\Lambda$ with $x\neq y$. I will use ${\rm Part}(\Lambda)$ to denote the set of set partitions of $\Lambda$. The polyhedron $K_1$ I am interested in lives in the vector space $$ V=\mathbb{R}^{\Lambda^{(2)}}\ . $$ A vector $v$ is therefore a collection of real numbers $v=(v_{\{x,y\}})_{\{x,y\}\in\Lambda^{(2)}}$ indexed by unordered pairs of elements in $\Lambda$, i.e., edges of the complete graph with vertex set $\Lambda$. To a partition $\Pi\in{\rm Part}(\Lambda)$, let me associate a vector $v_{\Pi}$ in $V$ whose components $v_{\Pi,\{x,y\}}$ are, by definition, equal to $1$ if $x,y$ are in the same block of partition $\Pi$, and equal to $0$ otherwise.

Definition: The set $K_1$ is the convex hull of all the $v_{\Pi}$, with $\Pi\in{\rm Part}(\Lambda)$.

I am also interested in the subset $K_2\subset K_1$ which is defined as follows. If $\Pi_1,\Pi_2$ are two partitions, we write $\Pi_1\preccurlyeq\Pi_2$ if all blocks of $\Pi_1$ are contained in blocks of $P_2$, i.e., $\Pi_1$ refines $\Pi_2$. Let $K_2$ be the set of all convex combinations $$ \alpha_1\ v_{\Pi_1}+\alpha_2\ v_{\Pi_2}+\cdots+\alpha_{\ell} \ v_{\Pi_{\ell}} $$ where the $\alpha$'s are nonnegative and add up to $1$, and where $$ \Pi_1\preccurlyeq\Pi_2\preccurlyeq\cdots\preccurlyeq\Pi_{\ell} $$ is a chain in the poset $({\rm Part}(\Lambda),\preccurlyeq)$.

An alternate description using real symmetric matrices is as follows. Let $\widetilde{V}$ be the vector space of real symmetric matrices $M=(M(x,y))_{x,y\in\Lambda}$ with rows and columns indexed by $\Lambda$ (e.g., $\Lambda=[n]:=\{1,2,\ldots,n\}$, for more comfort). To a $v\in V$ one can associate a matrix $M\in\widetilde{V}$ by letting $M(x,y)=v_{\{x,y\}}$ if $x\neq y$, and letting $M(x,x)=1$ for all $x\in\Lambda$. Let $\widetilde{K}_2\subset\widetilde{V}$ be the image of $K_2$ by the map just defined. It is not hard to see that the symmetric matrices $M$ in $\widetilde{K}_2$ are characterized by the following properties.

  1. For all $x,y\in\Lambda$, we have $0\le M(x,y)\le 1$.
  2. For all $x\in\Lambda$, we have $M(x,x)=1$.
  3. For all $x,y,z\in\Lambda$, we have $M(x,z)\ge\min(M(x,y),M(y,z))$.

My coauthor Greg W. Anderson, for the unpublished paper "Counting colored planar maps free-probabilistically" (see Section 2.1.1), called these co-ultrametrics because, modulo reversal of inequalities, this is reminiscent of the definition of an ultrametric distance. I love this name very much, but I don't know if there is a standard name already.

My question: Did $K_1$, appear in the literature, and does it have a name like associahedron, permutohedron, ...hedron? Also, is there a name for $K_2$ or its avatar $\widetilde{K}_2$?

My motivation: I am currently teaching a course on mathematical quantum field theory "for undergrads" and will soon need to talk about these sets. I would like to use the most appropriate terminology.

$\endgroup$
7
  • $\begingroup$ I put the algebraic topology tag because of possible connection to the partition lattice which plays a role, e.g., in Goodwillie calculus. $\endgroup$ Mar 26, 2023 at 17:42
  • 2
    $\begingroup$ Are you sure that your two descriptions define the same space? Let $\Lambda=\{1,2,3\}$. Then $\Lambda^{(2)}$ also has three elements. $K$ is the convex hull of $\{(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)\}$. On the other hand $\widetilde K$ seems to be homeomorphic to the space of triples $(x, y, z)$, where $0\le x,y, z\le 1$ and the three numbers do not have a strict minimum. This is homeomorphic to the union of three triangles that share an edge. The two spaces are not homeomorphic. The latter space is homeomorphic to the realization of the poset of partitions of $\{1, 2, 3\}$. $\endgroup$ Mar 27, 2023 at 5:20
  • 3
    $\begingroup$ @GregoryArone Specifically, in your example there are points in the image of $K$ that do not satisfy condition 3. Indeed image of $K$ consists of all matrices of the form$$M=\left( \begin{array}{ccc} 1 & \frac{a_{12}+a_{123}}{a_0+a_{12}+a_{13}+a_{23}+a_{123}} & \frac{a_{13}+a_{123}}{a_0+a_{12}+a_{13}+a_{23}+a_{123}} \\ \frac{a_{12}+a_{123}}{a_0+a_{12}+a_{13}+a_{23}+a_{123}} & 1 & \frac{a_{23}+a_{123}}{a_0+a_{12}+a_{13}+a_{23}+a_{123}} \\ \frac{a_{13}+a_{123}}{a_0+a_{12}+a_{13}+a_{23}+a_{123}} & \frac{a_{23}+a_{123}}{a_0+a_{12}+a_{13}+a_{23}+a_{123}} & 1 \\ \end{array} \right)$$ $\endgroup$ Mar 27, 2023 at 6:52
  • 2
    $\begingroup$ Here e. g. $M(1,3)\geqslant\min(M(1,2),M(2,3))$ might fail - it is violated, for example, if $a_{13}=0$ and $a_{12},a_{23}>0$. $\endgroup$ Mar 27, 2023 at 6:53
  • 1
    $\begingroup$ @AbdelmalekAbdesselam Don't be sorry please, it is fun to look into this $\endgroup$ Mar 27, 2023 at 15:32

1 Answer 1

5
+50
$\begingroup$

As I said in the comment, it seems to me that your two definitions are not equivalent. For example, the first definition yields a convex set, while the second one does not. I sort of hope and suspect that it is the second one that you want, because it is the more interesting space.

I believe that your second definition describes a space homeomorphic to the geometric realisation of the poset of partitions of $\Lambda$. Let $M$ be a symmetric matrix satisfying your conditions 1-3. Suppose $0\le s \le 1$. Define a relation on $\Lambda$ by saying that $x\sim y$ if $M(x, y)\ge s$. Your conditions guarantee that it is an equivalence relation on $\Lambda$, i.e., a partition. Moreover, if $0\le s_1\le s_2\le 2$, then the partition associated to $s_2$ is a refinement of the partition associated to $s_1$. It follows that every matrix $M$ satisfying your conditions can be written uniquely as a convex combination of basic matrices associated to a nested chain of partitions of $\Lambda$. This is precisely saying that $\widetilde K$ is homeomorphic to the realisation of the poset of partitions of $\Lambda$.

This is a contractible space, but is not a polyhedron. If it was a polyhedron, then its relative boundary would be homeomorphic to a sphere. As it stands, the boundary is homotopy equivalent to a wedge of sphere.

A couple of comments: First, a similar (but I think not homeomorphic) model for the partition complex was considered by Brenda Johnson in her paper "Derivatives of homotopy theory". This is the first paper where you can see a connection between the partition complex and Goodwillie calculus (but the partition complex is not named explicitly).

Second, this space is also closely related to the space of phylogenetic trees, which was studied for example by Biller, Holmes and Vogtmann in an influential paper called "Geometry of the space of phylogenetic trees".

$\endgroup$
3
  • $\begingroup$ Hi Greg. Thank you for your answer and sorry for messing up my question. I misremembered things I worked on (with the other Greg) 10 years ago :) I am interested in all these sets, even the polyhedron $K_1$ which is less interesting from your topological standpoint. Is there a reference you can recommend to learn quickly and efficiently about geometric realizations of posets? $\endgroup$ Mar 27, 2023 at 14:58
  • 2
    $\begingroup$ Right, $K_2$ is the geometric realisation of the poset of partitions, a.k.a the space of phylogenetic trees. The geometry of this space has been studied quite extensively. In addition to the paper of Billera, Holmes and Vogtmann, I might recommend "Convexity in Tree Spaces" by Lins, Sturmfels, Tang and Yoshida. $K_1$ is the convex hull of $K_2$. I don't know if anyone considered it explicitly or gave it a name. You can read about geometric realisation of posets in any introduction to combinatorial topology. I can recommend the survey paper by Wachs "Poset Topology: Tools and Applications". $\endgroup$ Mar 27, 2023 at 15:11
  • $\begingroup$ Again thank you for the answer. $\endgroup$ Mar 31, 2023 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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