**10**

votes

**2**answers

846 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 ...

**1**

vote

**1**answer

142 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$ ...

**9**

votes

**0**answers

254 views

### Weighted sum of the Simsun (Andre) permutations

Let $ c_{n,k} $ be the Simsun permutations$^1$ defined by the following relations: $\displaystyle c_{n,0} = 1, \hspace{0.1cm} (n \ge 1);$
$$ c_{n,k} = (k+1) c_{n-1,k} +(n-2k+1) c_{n-1,k-1}, ...

**7**

votes

**0**answers

77 views

### A separation property of graphs of bounded tree-width

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)
Let $T$ be a tree and $r, m$ ...

**5**

votes

**0**answers

118 views

### Growth in families of trees

I'm hoping that the question below is simple thermodynamic formalism, but I can't quite make it work. Any help would be very welcome.
Let $\Sigma:=\{0,1\}^{\mathbb N}$ and let $\Sigma^*$ be the set ...

**4**

votes

**0**answers

97 views

### Using Crump-Mode-Jagers processes to get logarithmic bound on a random tree height

I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I ...

**4**

votes

**0**answers

560 views

### Questions about dessin d'enfants, trees and their Shabat polynomials

This will be a series of questions, a few of which have been troubling me for quite a while now. Before I jump right in, let me first introduce a few notions which I will assume.
(Note: All of these ...

**2**

votes

**0**answers

70 views

### Factors between IID on trees: what about the useless information?

Let $p \in (0,1)$. Take $E$ to be the edge set of the trivalent tree $T$, and $G$ to be the automorphism group of $T$. Let $f$ be any $G$-equivariant map from the measure space $([0,1]^E, ...

**2**

votes

**0**answers

51 views

### Is there a name for this variant of the MST and the TSP?

Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as ...

**2**

votes

**0**answers

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.
...

**2**

votes

**0**answers

105 views

### Finding the number of leaf nodes at specific level of a random tree

Given a uniform recursive tree (URT) of size $N$ rooted at one node whereby the tree is generated as follows:
Starting with a root node, at each iteration, a new node is connected to one of the ...

**2**

votes

**0**answers

104 views

### Groups acting on non-locally-finite trees with independence and specified local actions

Suppose I have a biregular tree $T_{m, n}$ (not necessarily locally finite), with distinct cardinal numbers $m, n$, so Aut$(T_{m, n})$ acts on $T_{m, n}$ without inversion. Let $V_m$ be those vertices ...

**2**

votes

**0**answers

880 views

### Matula-Goebel ordering of rooted trees intrinsic?

I was somewhat recently introduced to the Matula-Goebel bijection between rooted trees and natural numbers. (nicely illustrated here http://keithbriggs.info/matula.html) Looking through them, I ...

**1**

vote

**0**answers

77 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 ...

**1**

vote

**0**answers

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 ...

**1**

vote

**0**answers

53 views

### Solutions for n such that the path number to the n-th node is also n in a complete, rooted, ordered k-ary tree

The path to find the $n$-th node within a complete, rooted, ordered $k$-ary tree can be represented by a number to the base $(k+1)$ that contains no zero digits. See A245905 in OEIS as an example for ...

**1**

vote

**0**answers

141 views

### Database of non-isomorphic trees

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

**1**

vote

**0**answers

246 views

### Is the automorphism group of a homogeneous (locally finite) tree unimodular?

I have seen somewhere (that I don't remember now) that the (full) automorphism group of a k-regular tree is unimodular. I assume a k-regular tree is the same thing as the homogeneous tree of degree k ...

**0**

votes

**0**answers

28 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) ...

**0**

votes

**0**answers

24 views

### Tree decompositions in linear hypergraphs

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a finite set and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \in L$ ...