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.

**6**

votes

**1**answer

106 views

### Are there Prüfer sequences for rooted forests?

One well-known, extremely slick proof of Cayley's tree enumeration theorem is the use of Prüfer sequences. Cayley also proved a version for forests, namely that the number of forests with $n$ ...

**0**

votes

**0**answers

51 views

### algorithm for maximum sum from root to leaf in a tree (non-binary)

Given some tree with vertices each that can have some variable number of children, is there some algorithm to find the maximum sum from the top of the tree down to one of the leaves? I can see one way ...

**7**

votes

**1**answer

108 views

### Two disjoint trees

Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ independent if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which ...

**6**

votes

**0**answers

67 views

### Partitioning the vertices of a graph into induced trees

I am looking for previous work regarding graphs whose vertices can be assigned colours (not necessarily a proper colouring) in such a way that each colour class induces a tree.
In particular I am ...

**1**

vote

**0**answers

24 views

### The number of Laplacian eigenvalues of a graph in interval [k,n]

There are several upper and lower bounds for $m_G[2,n]$ (the number of Laplacian eigenvalues of a graph $G$ with $n$ vertices in the interval $[2,n]$).
I want to know whether there exists any bound ...

**5**

votes

**1**answer

177 views

### Counting promenades on graphs

Let a "promenade" on a tree be a walk going through every edge of the tree at least once, and such that the starting point and endpoint of the walk are distinct. What we mean by isomorphic promenades ...

**1**

vote

**0**answers

42 views

### Shattering/covering finite trees, and a simple looking inequality

Consider the tree $T$ with the set of its maximal elements (denoted $[T]$) equal to $\prod_{m\leq n} X_m$ for some finite sets $X_0,..., X_n$. Let $p(T)=\{b: b\in \prod_{i\leq m \leq j } X_{m}\text{ ...

**6**

votes

**1**answer

247 views

### A permutation problem

Here I ask a question on permutations of $n$ distinct real numbers.
QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...

**1**

vote

**0**answers

34 views

### Family of rooted trees parameterized by binary sequences

Let $A=\{1,2\}$. For any $d \in A$ and any sequence $a=(a_1,a_2,\dots)\in A^{\mathbb N}$ the associated rooted tree $T(d,a)$ is recursively defined in the following way. The degree of the root of $T(d,...

**3**

votes

**0**answers

61 views

### Which spaces are still Lindelöf after forcing with a Suslin tree?

Let $T$ be a Suslin tree and $f:T\to Y$ be continuous. ($T$ is endowed with the order topology.) Assume that the image of $T$ is contained in a Lindelöf subset of $Y$. Then, force with $T$. Which ...

**7**

votes

**1**answer

620 views

### Is there a natural relationship between OEIS A127670 and Cayley's tree formula?

I apologize in advance that this question must sound highly amateurish, but I am wondering if there is any connection between the formula https://oeis.org/A127670 , which counts the number of fixed $n$...

**2**

votes

**2**answers

253 views

### How to label a tree with minimum cost?

Let $T = (V, E)$ be a tree. Let $\Sigma$ be a finite set of labels. Given a label function $\ell : V \to \Sigma$, the cost of $\ell$ is given by
$$\mu(\ell) = \left| \{(u,v) \in E \mid \ell(u) \neq \...

**3**

votes

**1**answer

119 views

### Trees and Shabat polynomials

Recently, I read the relation between Shabat polynomials and trees. The book [0] says that if $p: \mathbb{C} \to \mathbb{C}$ is a degree-$n$ polynomial such that the segment $[-1,1]$ contains no ...

**4**

votes

**2**answers

131 views

### Asymptotics of unrooted labeled forests

It is well known that the number of unrooted labeled trees on vertex set
$[n]={1,2,...,n}$ is $n^{n-2}$. Let $U(z)$ be the exponential generating function of the sequence of these numbers. Then $F(z)=\...

**4**

votes

**0**answers

102 views

### algebraic connectivity of a tree

Suppose that $T$ is a tree with $n$ vertices and $L$ is the Laplacian matrix of $T$ and $0=\mu_1 \leq \mu_2 \leq \cdots \leq \mu_n$ are laplacian eigenvalues.
I think the multiplicity of $\mu_2$ can ...

**1**

vote

**1**answer

71 views

### Term for the maximum number of vertices per depth of a rooted tree

I am searching for a term that describes the following property of a rooted tree (or actually a DODAG, but that should not make a difference) and preferably for a publication that uses/introduces this ...

**3**

votes

**2**answers

131 views

### Percolation on finite irregular trees

Consider a rooted tree of height $h$, such that all the leaves are at last layer. We perform the following random process: each edge is deleted with probability $0.5$, and otherwise it is retained. We ...

**1**

vote

**0**answers

53 views

### Automorphism groups of graphs of bounded treewidth

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become ...

**5**

votes

**1**answer

294 views

### Growth rate of longest sequence of strings where no string is a subsequence of a later one

We define $STR(n)$ to be the longest sequence of strings with $n$ symbols such that the $k$th string has at most k symbols, the symbols of the string are taken from an alphabet consisting of $n$ ...

**7**

votes

**0**answers

113 views

### A non-special Aronszajn tree with a stationary set that is non-stationary with respect to the tree

Is there any example of a ($\omega_1$-)Aronszajn tree $T$ that is non-special and there exists a stationary subset $S\subset \omega_1$ such that $S$ is not stationary with respect to $T$?
A tree ...

**3**

votes

**1**answer

124 views

### Number of independent sets of a random tree

Let $T_n$ be a random tree on $n$ labelled vertices chosen equiprobably among all $n^{n - 2}$ trees, and $I(T)$ be the number of distinct independent sets of a tree $T$. I'm interested in the average ...

**5**

votes

**2**answers

229 views

### Automorphism of the transfinite rooted binary tree

I was studying combinatorical group theory recently, and I came across the infinite regular rooted binary tree and its automorphism group $Aut(T^{(2)})$with the Grigorchuk subgroup.
Let me now ...

**7**

votes

**1**answer

229 views

### Spanning $k$-trees

k-trees
A $k$-tree is a graph defined as follows: (They were defined by Harary and Palmer.)
a) A complete graph with $k$ vertices is a $k$-tree.
b) A $k$-tree on $n$ vertices $T$ is obtained by a $...

**0**

votes

**1**answer

141 views

### Bound on queries to a tree with unusual probabilties — follow-up

This question follows up on Bound on queries to a tree with unusual probabilities, where @fedja was able to disprove my conjecture under only constraints (1-4) below. I restate the relevant facts here ...

**12**

votes

**0**answers

300 views

### The number of labeled pairs of edge disjoint trees and related questions

I wonder what is known on the following:
1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices?
2) (harder, it seems) What ...

**7**

votes

**1**answer

189 views

### Bound on queries to a tree with unusual probabilities

Consider a tree $\mathcal{T}(r) = (V,E)$ rooted at $r \in V$. Let $\kappa_r: V \longrightarrow [0,1]$ such that $\sum_{v \in V} \kappa_r(v)^2 = 1$. Furthermore, for any given vertex $v \neq r$, $\...

**2**

votes

**0**answers

55 views

### excursion decomposition of random walk on a tree

It's a nice exercise to show the following decomposition of a simple random walk on an infinite $(d+1)$-regular tree into a nonbacktracking walk with independent excursions. Hopefully I got all the ...

**7**

votes

**1**answer

234 views

### Counting some binary trees with lots of extra stucture

While working on some computations on Hilbert schemes, I came across the following combinatorial problem.
Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ ...

**2**

votes

**0**answers

102 views

### Using the Bruhat-Tits tree for unitary groups

For now I always worked in the setting of the Bruhat-Tits tree in the $SL(2)$ setting (like in the book of Serre), without any further background about Bruhat-Tits buildings. I would like to adapt ...

**2**

votes

**0**answers

99 views

### Cardinality of compact doubling metric spaces with fast growing covering numbers

In this question it was established that if the growth of the number of branches of an at-most $k$-branching tree is $\Omega(k^n)$ (in the Knuth sense), then the tree has continuum many branches.
...

**9**

votes

**2**answers

697 views

### History of deletion-contraction formula

The following is known as deletion-contraction formula:
Assume $\Gamma$ is a connectted graph with edge $\rho$ then
$$t(\Gamma)=t(\Gamma\backslash\rho)+t(\Gamma/\rho),$$
where $\Gamma\backslash\...

**7**

votes

**1**answer

211 views

### Bijective proof of formula for rooted binary forests

For $n\ge 1$, let $f(n)$ be the number of rooted complete (unordered) binary trees with $n$ leaves labeled from $1$ to $n$ ("complete binary" means that every vertex has either $0$ or $2$ children and ...

**7**

votes

**1**answer

326 views

### Drawing trees on small number of lines in 2D and 3D

Problem. Given a tree do we need fewer lines in 3D than in 2D in order to draw it straightline and crossing-free?
(Asked 01.10.2016 by Alexander Wolff, see page 20 on http://www.math.lviv.ua/szkocka/...

**3**

votes

**1**answer

146 views

### Inferring tree graph from distance matrix

Given a $n$x$n$ distance matrix of some undirected weighted tree graph, is it possible to infer the underlying tree and its edge weights?
For example, suppose we are given the following distance ...

**2**

votes

**2**answers

264 views

### An approximation for the number of subtrees of a tree

Let $T$ be a labeled tree with the root $v$, such that:
$(i)$ The height of the tree is $x$,
$(ii)$ the degree of the vertex $v$ is $y-2$,
$(iii)$ the degree of each vertex, except the leaves and ...

**2**

votes

**1**answer

60 views

### Modifying tree Graphs

Please consider a tree graph. There is one unique path connecting any two vertices.
However, I wonder how to address the following question:
Starting from a generic tree, is there an algorithmic way ...

**2**

votes

**0**answers

89 views

### Does there exist a linear-time algorithm to find a basis of the null space of the adjacency matrix of a tree?

I am working on a decomposition of trees based on the null space of the adjacency matrix of the tree. Most algorithm on trees are really fast. The decomposition could give some algorithms to find ...

**1**

vote

**0**answers

53 views

### Root degree in large subcritical Galton-Watson trees

Let $\mathcal{T}_n$ denote a subcritical Galton-Watson tree conditioned on having $n$ vertices. Assume that the offspring distribution $\xi$ is heavy-tailed and that there is an integer $k_0$ with
$$
\...

**0**

votes

**0**answers

225 views

### Does a finite group acting on a tree have a fixed point?

In "Groups Acting on Graphs" by W. Dicks and M.J.Dunwoody, they prove the following proposition (4.7):
"Let $v$ be a vertex of a $G$-tree $T$, where $G$ is a group. Then $G$ stabilizes a vertex of $T$...

**0**

votes

**1**answer

101 views

### A method to find the number of points contained inside the rectangle in O(log n ^2 ) worst case with precomputation?

Given a set of 2 - D points (with integer x and integer y coordinates) and a set of queries containing the coordinates of a rectangle(integers).

**4**

votes

**0**answers

73 views

### Non-convex optimization problem involving minimum spanning trees

Suppose I am given $n$ points $p_1,\dots,p_n\in \mathbb{R}^2$, as well as two positive coefficients $a_1$ and $a_2$, and I am trying to select $n$ points $x_1,\dots,x_n$ to solve the following ...

**1**

vote

**0**answers

67 views

### Relationship between weight of spanning tree in a tree metric approximation and the original metric

So suppose we have a tree metric which approximates the Euclidean distance between a finite set of points. The leaves correspond to points in the original space. It may be an ultra metric, and ...

**1**

vote

**1**answer

116 views

### Some references to understand the proof of a theorem about simple random walk on galton watson trees

Mathematicians Lyons,Pemantle and Peres have proved in the paper entitled "Ergodic Theory on Galton-Watson Trees: Speed of Random Walk and Dimension of Harmonic Measure" that the speed of a simple ...

**0**

votes

**0**answers

91 views

### How to get some information about a random variable if we know very little about its distribution

Suppose that $X, Y$ are random variables,both from a probability space to $(0,\infty]$, such that X and $1+Y$ have the same distribution, $Y=Z_1$ with probability equals half, otherwise $Y= \frac{...

**4**

votes

**1**answer

425 views

### What is a universal tree?

I came across some slides talking about the Hrushovski construction. One of the examples was the construction of a "universal tree".
I was curious because the collection of finite trees does not ...

**0**

votes

**0**answers

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

**1**

vote

**0**answers

434 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

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

**7**

votes

**1**answer

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

**2**

votes

**0**answers

75 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^{\...