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.

learn more… | top users | synonyms

2
votes
1answer
57 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
0answers
45 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
2answers
140 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
1answer
162 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
1answer
100 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
2answers
152 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 ...
0
votes
1answer
90 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
0answers
70 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
1answer
281 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 ...
2
votes
0answers
39 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. ...
9
votes
0answers
180 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}, ...
3
votes
1answer
57 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
1answer
154 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
1answer
278 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
1answer
202 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
0answers
64 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
1answer
208 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 ...
9
votes
1answer
411 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
1answer
179 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
1answer
337 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
1answer
230 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
1answer
184 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
0answers
52 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
2answers
497 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
3answers
420 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
0answers
116 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
2answers
128 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 ...
10
votes
1answer
294 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
2answers
281 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
1answer
167 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). ...
1
vote
1answer
137 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 ...
6
votes
1answer
244 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
2answers
272 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
1answer
241 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 ...
15
votes
0answers
628 views

Souslin trees and weakly compact cardinals

In Souslin trees on the first inaccessible cardinal it is asked if it is consistent that there are no $\kappa-$Souslin trees at the least inaccessible cardinal $\kappa$. In this question I would like ...
5
votes
2answers
238 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
0answers
102 views

Database of non-isomorphic trees

As there are several free prime number databases, is there something similar for non-isomorphic trees?
2
votes
0answers
91 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 ...
7
votes
0answers
128 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
1answer
405 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
2answers
295 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
1answer
526 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
1answer
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 ...
2
votes
2answers
164 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 ...
9
votes
4answers
603 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 ...
3
votes
2answers
510 views

A structure of the group of automorphisms of an infinite binary tree

My friend asked me to ask his question here. Where he can find (a paper or a book) containing a complete description (with the proof) of a structure of the group of automorphisms of an infinite binary ...
9
votes
1answer
338 views

Suslin trees in ccc ideals

A countably complete ideal $I$ on a set $Z$ ideal is c.c.c. when there is no uncountable family of pairwise disjoint $I$-positive subsets of $Z$. If such an ideal exists, then there exists a weakly ...
9
votes
3answers
350 views

Characteristic polynomials of trees and E8

In thinking about constructing manifolds via surgery or plumbing, the following combinatorial problem comes up: If T is a tree with adjacency matrix A and I is the identity matrix of the same order, ...
4
votes
0answers
88 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 ...
10
votes
2answers
809 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 ...