**23**

votes

**9**answers

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

**22**

votes

**2**answers

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

**13**

votes

**1**answer

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

**11**

votes

**5**answers

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

**9**

votes

**4**answers

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

**9**

votes

**1**answer

222 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

**2**answers

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

**9**

votes

**1**answer

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

**9**

votes

**0**answers

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

**8**

votes

**3**answers

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

**8**

votes

**1**answer

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

**7**

votes

**2**answers

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

**6**

votes

**0**answers

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

**5**

votes

**2**answers

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

**5**

votes

**2**answers

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

**5**

votes

**2**answers

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

**3**

votes

**2**answers

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

**3**

votes

**1**answer

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

**3**

votes

**1**answer

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

**3**

votes

**2**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

366 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

**2**answers

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

**2**

votes

**1**answer

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

**2**

votes

**1**answer

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

**2**

votes

**1**answer

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

**2**

votes

**1**answer

198 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

**0**answers

34 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

**1**answer

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

86 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

313 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

**2**answers

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

**1**

vote

**1**answer

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

**1**

vote

**0**answers

100 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

84 views

### Database of non-isomorphic trees

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