# Questions tagged [trees]

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.

**7**

votes

**1**answer

372 views

### Destroying Suslin, nothing special

Recall that a tree on $\omega_1$ is called Suslin if every chain and antichain are countable. If every level is countable and there are no cofinal branches, then it is called Aronszajn (in particular ...

**3**

votes

**1**answer

69 views

### Typical labelled vs. unlabelled trees properties

Consider two random tree models $T_1(n)$ and $T_2(n)$, chosen equiprobably among labelled and unlabelled trees on $n$ vertices respectively. I'm wondering if there are properties that are vastly more ...

**10**

votes

**2**answers

281 views

### Almost graceful tree conjecture

The graceful tree conjecture is the following statement: for any tree $T = (V, E)$ with $|V| = n$ there is a bijective map $f: V \to [n]$ such that $D = \{|f(x) - f(y)| \mid xy \in E\} = [n - 1]$.
...

**0**

votes

**1**answer

232 views

### A monad that unions sets

Suppose we have a monad that maps types of some kind to other types (see below) , and let types be sets. Let $\alpha, \beta$ be types, $\rightarrow$ denote a function between types, and let $a : \...

**6**

votes

**1**answer

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

**7**

votes

**1**answer

109 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

31 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

179 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

262 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

37 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

62 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

623 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

258 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

121 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

133 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

105 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

132 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

54 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

296 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

116 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

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

**6**

votes

**2**answers

239 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

235 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

142 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

190 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

56 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

245 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

107 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

100 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

705 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

363 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 on page 20 of Volume 1 of the Lviv Scottish Book)...

**3**

votes

**1**answer

150 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

280 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

61 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

55 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

235 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

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

**2**

votes

**0**answers

71 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

120 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

92 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

430 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

79 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

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