# Tagged Questions

A tree is a connected graph without cycles, with a finite or infinite number of vertices. There are many variants of trees, according to further constraints or decorations.

15 views

### What is a universal tree?

I came across some slides talking about the Hrushovski construction. One of the examples was the construction of a "universal tree". I was curious because the collection of finite trees does not ...
170 views

### Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
47 views

### Solving Recursive Expression for Counting Unrooted Tree Topologies

The book Bayesian Evolutionary Analysis with BEAST by Alexei J. Drummond et al. (2015) states at section 2.2.1 that the number of rooted unlabelled (binary) tree topologies $a_n$ is given by the ...
894 views

### Translation length functions of non-simplicial trees

Let $G$ be a finitely generated group. By a theorem of Culler and Morgan, the set of non-abelian (not necessarily simplicial) minimal $\mathbb{R}$-trees with isometric $G$-action injects into the ...
85 views

### Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching of maximal cardinality. A tree is an acyclic connected graph. Is there an efficient ...
31 views

### Similarity metric for labelled weighted graph/minimum spanning tree

I'm looking for a metric to measure similarity of minimum spanning trees of labelled weighted graphs. Each entity to compare has the same nodes (number of nodes and labels identical) but (unlabelled) ...
140 views

### Can a surface group act on a finite-valence simplicial tree?

Question. Let $S$ be a closed surface of genus $> 1$. Can $\pi_1(S)$ act faithfully and minimally on a simplicial tree of finite valence? Here "minimal" means that there is no invariant sub-tree. ...
164 views

140 views

### Counting growing tree trajectories

I am looking for help: Beginning with a single node ($\circ$), at each discrete time step I can add a node/link pair to any node currently in the tree. Nodes are unlabelled and the tree is ...
143 views

### Database of non-isomorphic trees

As there are several free prime number databases, is there something similar for non-isomorphic trees?
280 views

### Partitioning a binary tree into vertex-disjoint subtrees

Say we have a labeled, binary unrooted tree $T$, i.e. each node has either 1 or 3 neighbors. Denote by $L(T)$ the set of leaves (degree-one nodes) of $T$. For some $L \subseteq L(T)$, denote by $t(L)$...
89 views

40 views

### LDP respectively almost sure convergence in the context of randomly weighted trees

I am currently working on the following Problem: Imagine you are given a $d$-ary tree $T_d$, which means an infinite tree with one vertex $x_0$ on top and in which each vertex has $d$ children. Next,...
65 views

### Billera Tree Space

I am studying the tree space of Billera and I do not really understand why it is an Hadamard Space. I have already read L. Billera, S. Holmes, K. Vogtmann, Geometry of the space of phylogenetic trees, ...
173 views

### How to uniquely define a tree? [closed]

In an undirected unlabled graph $G=(V,E)$, we want to find a tree as a subgraph, such that the graph can be decomposed into edge disjoint trees(all the tress are isomorphic). How to define such a tree ...
286 views

### Computing the probability of reaching any leaf of an $n$-ary infinite probability tree

Suppose you have two players $X$ and $Y$ fighting, both of which have $n\in \mathbb{N}, n\geq1$ life. Each player has a probability $p_i$ of doing $i$ damage for all $i\in[0, n]$. Note that $p_0$ is ...
216 views

### Counting trees according to endpoints

Question: Is there a nice (or any) formula for the generating function $$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$ where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints? ...
349 views

### The number of monotone full binary trees

Let $\rho$ be an equivalence relation on a semigroup $S$. A subsemigroup $S'$ of $S$ is called a $\rho$-cross-section of $S$, provided that $S'$ contains exactly one representative from each ...
68 views

### Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
420 views

412 views

### More asymptotics for trees

This is a follow up to my recent question on the asymptotics of A003238. Lucia gave a fine answer to that question, but as I hinted the 'real' problem I have in mind is slightly different, and I've ...
297 views

### Is not SH + not CH consistent?

I guess that $\lnot$SH + $\lnot$CH is consistent, but I have not found this question discussed anywhere. Is there any relatively simple model of $\lnot$SH + $\lnot$CH?
147 views

### Ratio of expected diameter and height of a conditioned Galton-Watson tree

A Galton-Watson tree is the family tree of a Galton-Watson process. Let $T_n$ denote a Galton-Watson tree conditioned on total population size $n$. The time of extinction is its height $H(T_n)$ and ...
168 views

### Switching representatives of right coset in a paper on fundamental domain of tree of GL(2)

I have a question concerning the following paper: "The fundamental domain of the tree of GL(2) over the function field of an elliptic curve" by Shuzo Takahashi. (1993, Duke Math. J., Vol. 72, No. 1). ...
276 views

### Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...
For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of $y$...