**1**

vote

**0**answers

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

**0**

votes

**0**answers

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

**6**

votes

**1**answer

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

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

**2**

votes

**0**answers

71 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, \text{d}x^{\...

**2**

votes

**1**answer

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

**2**

votes

**1**answer

86 views

### Spectrum of Laplacian matrix of an infinite tree graph

I'm having difficulty understanding a fact stated in a research paper I'm reading. Namely, let $T$ be a tree with all nodes of degree $4$ (ie, the root has $4$ daughter nodes and all other nodes have $...

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

**6**

votes

**2**answers

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

**3**

votes

**1**answer

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

**2**

votes

**1**answer

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

**3**

votes

**2**answers

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

**1**

vote

**1**answer

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

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

**6**

votes

**1**answer

293 views

### Embedding of real trees into $\ell_1(\Gamma)$

It seems plausible that any real tree or ${\mathbb{R}}$-tree in the sense of the definition in https://en.wikipedia.org/wiki/Real_tree admits an isometric embedding into the Banach space $\ell_1(\...

**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.
Next,...

**9**

votes

**0**answers

256 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}, \hspace{0....

**3**

votes

**1**answer

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

**1**

vote

**1**answer

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

**2**

votes

**1**answer

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

**4**

votes

**1**answer

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

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

**3**

votes

**2**answers

276 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)$...

**9**

votes

**1**answer

418 views

### Is $\clubsuit_{\omega_1}$ enough to get Suslin tree?

This is problem 15.3 in Arnie Miller's problem list:
(Juhasz) Suppose there exists $\langle A_{\alpha} : \alpha \in L \rangle$, where $L$ is the set of limit ordinals below $\omega_1$ and for each $\...

**4**

votes

**1**answer

191 views

### Existence of $\kappa$-Suslin trees above a measurable cardinal

We have learned from Joel David Hamkins and Monroe Eskew that:
Answers:
Having a measurable cardinal $\delta$ we can force a $\kappa$-Suslin tree for many $\kappa$'s above $\delta$.
But is the ...

**4**

votes

**1**answer

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

**6**

votes

**1**answer

244 views

### Embedding Euclidean buildings into products of trees

A Euclidean building has a natural metric space structure. (A definition of Euclidean building can be found on Wikipedia, or, more expansively, in Section 4 of Kleiner-Leeb.)
Question: Is it true ...

**3**

votes

**1**answer

191 views

### Determinant of the oriented adjacency matrix of a tree

Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries
$$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\
-1 &...

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

**10**

votes

**2**answers

540 views

### Number of paths through infinite trees with given “growth rates”

(Preface: This may be a naive or easy question for experts....)
Consider an infinite tree, rooted on the left, where each node has two children; the number of nodes at each level (distance from the ...

**1**

vote

**3**answers

535 views

### Is there a formula for the number of labeled forests with $k$ components on $n$ vertices?

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. My question is: Is there a generalization of this formula for forests?
Let $f_{n,k}$ denote the number of ...

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

**7**

votes

**2**answers

134 views

### Trees with a maximal convex hull: are the only optimal solutions Steiner trees?

For given $n\geqslant 3$, I'm looking for a connected set composed of $n$ equal segments in the plane such that the convex hull of it has maximal area $A(n)$. To simplify notation, we'll take $\dfrac{...

**10**

votes

**1**answer

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

**2**

votes

**2**answers

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

**3**

votes

**1**answer

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

**3**

votes

**1**answer

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

**7**

votes

**1**answer

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

**4**

votes

**2**answers

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

**2**

votes

**1**answer

244 views

### A variant of Kruskal's theorem

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

**5**

votes

**2**answers

253 views

### Can we have a $\kappa$-Suslin tree where $\kappa$ is above a measurable cardinal?

Question: Can we have a set theory in which there exists a $\kappa$-Suslin tree with $\kappa$ larger than the least measurable cardinal?
A $\kappa$-Suslin tree is a tree with levels indexed by $\...

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

**2**

votes

**0**answers

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

**9**

votes

**1**answer

163 views

### A published proof for: the number of labeled $i$-edge ($i \geq 1$) forests on $p^k$ vertices is divisible by $p^k$

Let $F(n;i)$ be the number of labeled $i$-edge forests on $n$ vertices (A138464 on the OEIS). The first few values of $F(n;i) \pmod n$ are listed below:
$$\begin{array}{r|rrrrrrrrrrr}
& i=0 &...

**7**

votes

**1**answer

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

**5**

votes

**2**answers

313 views

### Average number of distinguished leaves in a binary tree

By a binary tree, I mean in this question a full rooted binary tree in which left and right child are labeled. A leaf of such a tree is a vertex of degree at most 1 (most references would probably ...

**13**

votes

**1**answer

536 views

### Are the asymptotics of A003238 known?

Sequence A003238 of the OEIS counts ``rooted trees with $n$ vertices in which vertices at the same level have the same degree.'' The sequence, $a$, begins
1, 1, 2, 3, 5, 6, 10, 11, 16, ...
and it is ...

**8**

votes

**1**answer

154 views

### Does being special on a club imply being special?

Let $T$ be an Aronszajn-tree, $C\subset \omega_1$ a club set and $f:\bigcup\limits_{\alpha\in C}T_\alpha\longrightarrow \mathbb Q$ a strictly increasing function (where $T_\alpha$ is the $\alpha$-...

**2**

votes

**2**answers

170 views

### Normal subgroups of automorphism group of infinite cubic tree

Let $T$ denote the unique (countably infinite) tree in which every vertex has degree $3$ and let $G=Aut(T)$ be the group of graph automorphisms of $T$.
I'm interested in the properties of this group,...

**9**

votes

**4**answers

631 views

### Are there two computable binary trees such that each has a branch not computing any branch through the other?

It is a well-known elementary classical result in computability theory that there are computable infinite binary trees $T\subset 2^{<\omega}$ having no computable infinite branch. (One can build ...