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

3
votes
1answer
151 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
37 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
367 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
99 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
98 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
118 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 ...
0
votes
0answers
21 views

Merging regions of function with similar mean and deviation using statistical test

I have got a question related to statistical tests that I would like to use in a new algorithm I am developing. Given an action space $x$, the algorithm would identify the regions in the function ...
10
votes
1answer
266 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
245 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
155 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
105 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
193 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
250 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
0answers
162 views

Relations between Arboreal Group Theory and Tree Group Actions? [closed]

By a tree group action, we mean an action of a group $G$ over the infinite regular binary tree $T_2$ such that for each $g \in G$, the mapping $x \mapsto g\cdot x$ is an automorphism of $T_2$; these ...
2
votes
1answer
227 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 ...
13
votes
0answers
568 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
181 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
93 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
44 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
114 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 ...
6
votes
1answer
389 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
234 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
456 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
148 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
135 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
494 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
365 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
300 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 ...
8
votes
3answers
306 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, ...
3
votes
0answers
53 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 ...
2
votes
0answers
97 views

Groups of automorphisms of weighted graphs

Let $\Gamma=(V,E,\omega)$ be an (edge-)weighted graph without loops and multiple edges. Here $V$ is the set of vertices, $E$ is the set of edges and $\omega:E \to \mathbb{N}$. A permutation $\varphi$ ...
1
vote
0answers
144 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 ...
2
votes
0answers
90 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 ...
4
votes
0answers
424 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 ...
1
vote
2answers
131 views

Are trees spectrally determined?

Are trees (connected acyclic graphs) determinable up to isomorphism by their spectra or characteristic polynomials? If not, what other pieces of information may help determine the tree?
2
votes
1answer
228 views

Hasse Diagrams of trees with height $>\omega^2$

I'm looking to improve my intuition and visualization of what large countable trees look like and I've ran into the issue that I have no understanding of what a tree of height, say, $\omega^2$ looks ...
2
votes
1answer
177 views

Group actions on trees and translates under hyperbolic elements

I have the following question regarding group actions on trees to which I suspect the answer to be "yes", but it could very well be that extra conditions are required (it is certainly true for free ...
3
votes
1answer
151 views

Correspondence between fractal sets and trees

In Hillel Furstenberg's series lectures on ergodic theory in fractal geometry, he mentioned his search on finding a one-to-one correspondence between fractal sets and trees, however, I couldn't not ...
8
votes
2answers
206 views

Distortion of tree embedding in Alexandrov spaces

It is a well-known theorem first proved by Bourgain that any map $\varphi:T_n\to H$ from the binary tree of height $n$ to a Hilbert space has distortion at least $C \sqrt{\ln n}$ where $C$ is a ...
2
votes
0answers
508 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 ...
9
votes
2answers
445 views

Series defined by a fixed-point functional equation

Description I my work, I met fixed-point functional equations of a very specific form. Since I am not expert in the domain of functional equations, I have not pushed the study of these very far. Here ...
23
votes
9answers
2k views

Is the empty graph a tree?

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed. The ...
2
votes
1answer
292 views

Sequent calculus: is there a complete linear reasoning (i.e., no trees)?

In Gentzen's sequent calculus, a formal proof is described by a tree, with each node representing the sequent obtained from the child(ren) by applying a given inference rule. If no inference rule has ...
22
votes
2answers
1k views

Does this poset have a unique minimal element?

Recently I have been thinking about the following poset: the underlying set is $\mathcal{AFT}$ consisting of all (finite) automorphism-free undirected trees (with at least one edge to exclude the ...
12
votes
5answers
884 views

Is the following invariant of rooted trees a complete invariant?

Recall that rooted trees may be generated by starting with a trivial rooted tree (just a vertex), along with the operations of grafting a number of trees (identify their roots) and adding a new vertex ...
5
votes
2answers
251 views

Number of trees with the same matching number

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$. I have been trying to compute the value of ...
9
votes
1answer
300 views

What is the precise relationship between “prodsimplicial sets” and rooted trees?

In Keven Walker's answer to the question, Cubical vs. simplicial singular homology it is written: Personally, I think it is more convenient to do singular homology with the larger collection ...
1
vote
1answer
489 views

Graph drawing: unrooted undirected tree graphs with specified edge lengths.

Has Joseph Felsenstein's equal daylight layout been analyzed by the graph drawing community? The following description is taken from his drawtree documentation: "This iteratively improves an ...
3
votes
2answers
573 views

Fixed points of a group-operation on a tree, Serre's book “Trees” 6.3.4. and Prop 27

Hello! I have a problem with the following Lemma, which is mentioned in Serre's book "Trees" on page 60. In the book it is the Example 6.3.4.: Lemma: Let $G$ be a group acting (without inversion) on ...
4
votes
1answer
199 views

A distinguishing node property in trees?

Consider a tree with k nodes and for each node v the vector lv = (lv0, lv1, ..., lvk-1) with lvd the number of leaves (!) with distance d to v. I wonder whether two nodes v, w with lv = lw are ...