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

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 ...
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. ...
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$ ...
71 views

52 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 ...
158 views

### a variant of the Kleene tree

The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known. I need a variant. (For those in the know, I need a c-bar which is ...
176 views

### A criterion for rooted trees to be isomorphic based on walks

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to ...
107 views

### Does anyone have the correct link to treewidth.com?

Several posts (and this) on StackExchange sites like MO have some link-rot. For example, I've been looking into tree decomposition and keep coming across references to treewidth.com, but the link ...
169 views

### on counting the number of trees on Kn (case)

During my reasearch I have stumbled across a problem that can be presented in such way: "How many are there spanning trees on Kn such that every tree contains v: deg(v) = k, for a given k" The ...
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$ ...
78 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$ ...
295 views

305 views

### Game on the tree [closed]

There's a problem from programming competition which already finished: http://codeforces.com/contest/458/problem/F Two weeks already passed but still nobody solved it yet - in fact you can see here ...
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?
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). ...
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 ...
321 views

### To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?

This is a cross-post from MSE. In the paper "Seven Trees In One" by Andreas Blass, a "very explicit" bijection is found between trees and 7-tuples of such trees. The idea to construct such a ...
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$...