Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
2answers
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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^{\...