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

222
questions

-1
votes

1
answer

62
views

### Strong law of large numbers for a sequence of random variables in different probability spaces

Is it known whether the following version of the strong law of large numbers holds?
For each $k\in\mathbb{N}$, let $\Omega_k$ be a finite set and $\mu_k$ be a probability measure on $\Omega_k$. Let $(...

5
votes

1
answer

331
views

### Thick Canadian trees

A Canadian tree (also called a weak Kurepa tree) is a tree of height $\omega_1$ with levels of cardinality $\leq \omega_1$ and at least $\omega_2$ many uncountable branches. Let's call a Canadian tree ...

4
votes

1
answer

321
views

### Action of braid groups on regular trees

Question:
Are there any well known actions of braid groups on trees? For example is there some action of a braid group $ B_n $ on a $ p $ regular tree for some $ p $ such that the action is transitive ...

1
vote

0
answers

62
views

### Fractal dimension of a self-similar tree

Consider a binary tree constructed as the following. Given a node with a some value $x$, I construct two children nodes each having value $l(x)$ and $r(x)$ respectively. I repeat the same on the ...

2
votes

0
answers

42
views

### Maximal cliques in neighborhood graphs of partial $k$-trees (bounded treewidth)

Background
My question is about a generalization of the following situation:
Let $M$ be a finite metric space. Given $r>0$, the $r$-neighborhood graph $N(M)_r$ has vertex set $M$ and an edge $\{x,y\...

0
votes

1
answer

40
views

### Minimum spanning tree and projection

Let $G$ be a graph of $n$ arcs and let $x\in \mathbb{R}^n$. I want to compute the orthogonal projection of $x$ onto the set of radial graphs with $k$ roots contained in $G$ (or a forest with $k$ root) ...

3
votes

1
answer

82
views

### Terminology for a subtree of a rooted tree with a path boundedness property

I'm not a graph theorist, so I apologize if some of the following terminology isn't quite correct.
Let $(T,f,v_0)$ be a complete degree $d$ rooted tree (definition at the end).
Definition. Let $m\ge0$....

2
votes

1
answer

73
views

### Characterization of graphs without leaves

Let $G(n,l)$ denote the set of connected graphs with $n$ vertices and $l$ edges and let $G_0(n,l)$ denote the elements of $G(n,l)$ without leaves. It is easily seen that $G_0(n,n-1)$ is empty, since $...

2
votes

0
answers

60
views

### Structure Theory for Tree Decompositions

I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...

1
vote

0
answers

62
views

### Standard terminology for node in tree with multiple children

Is there a standard terminology for a node in a tree that has multiple children?
For instance, in describing in perfect tree in $\omega^{< \omega}$ how would you describe the nodes that are ...

15
votes

2
answers

979
views

### A combinatorial interpretation for $n$-ary trees for negative $n$

The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation
$$
T_n=1+xT_n^n.
$$
This is usually defined for $n\ge 0$, but the functional equation can be ...

6
votes

1
answer

117
views

### Cofinal trees in $({}^\omega \omega , \leq^\ast )$

So, I know that the existence of a scale (that is, a linear cofinal set in $({}^\omega \omega , \leq^\ast )$, where $\leq^\ast $ is eventual domination, is equivalent to $\mathfrak{b} = \mathfrak{d}$, ...

2
votes

0
answers

90
views

### What is the analogue of a Block-Cut Tree Decomposition in directed graphs?

Let $G$ be a connected, undirected graph. We define a block $B$ to be a maximal $2$-connected induced subgraph in $G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ...

7
votes

0
answers

221
views

### In search of a quick proof that groups acting freely on $\mathbb R$-trees are linear

Many years ago I had the idea to use non-standard analysis to prove that a group acting freely on an $\mathbb R$-tree must be linear. The heuristic went like this:
A non-standard model $G^*$
of the ...

8
votes

1
answer

247
views

### First inaccessible Suslin trees in L, an interesting detail

It's known (but quite nontrivial) that $V=L$ implies that if $\kappa$ is the 1st inaccessible cardinal then there are $\kappa$-Suslin trees $T$.
Such a tree $T$ can be considered as a forcing notion ...

1
vote

0
answers

114
views

### Frog game on tree graphs is in NP but not in P (NP-complete)?

Problem
We can restrict ourselves to tree graphs. What is the complexity of the following problem?
Let $G$ be simple connected graph with vertices in $V$, edges in $E$, and a vertex weighted function $...

1
vote

1
answer

121
views

### Symmetry of infinite locally finite trees

Let $\Gamma$ be an infinite, locally finite tree without end points, with the additional property that there exists a positive integer $N$ such that for each occurring valency $v$, we have that $v \...

4
votes

1
answer

241
views

### In what sense is Bass-Serre theory the one-dimensional version of orbifold theory

The Wikipedia article on Bass-Serre theory claims that graphs of groups (in the context of Bass-Serre theory) "can be viewed as one dimensional versions of orbifolds." I hazily see a ...

1
vote

1
answer

151
views

### Tree width and clique width of regular graphs

Consider a $k$ regular graph of $n$ vertices, where $3 \leq k \leq (n-1)$. Is there any upper or lower bound, in the worst case, known for either the tree-width or the clique width of each $k$ regular ...

1
vote

0
answers

46
views

### How can we hang the weighted trees so that vertices nearer to root (based on distances, not hop count) lie in upper levels?

I have a set of edge weighted trees, each tree rooted at some vertex. Consider these trees are hung from the roots and vertices are arranged in some levels. I wish to design an algorithm (...

2
votes

0
answers

98
views

### Bruhat-Tits tree as Cayley graph of free group

$\DeclareMathOperator\BT{BT}\DeclareMathOperator\GL{GL}$Let $p > 2$ be a prime and $n = \frac{p + 1}{2}$. We can identify the vertices of Bruhat-Tits tree $\BT(\mathbb Q_p)$ with the elements in ...

2
votes

1
answer

144
views

### Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum

For $b,w \geq 0$ let $K_{b+1,w+1}$ be the complete bipartite graph with vertices $a_1,...,a_{b+1}$ on the left hand side and $c_1,...,c_{w+1}$ on the right hand side. For given $1 \leq d \leq w$ and $...

2
votes

1
answer

200
views

### Is there a formula for the number of trees with this extra condition?

A tree $G$ on $n$ vertices $V=\{v_1,...,v_n\}$ is a connected undirected graph which is acyclic. For each tree $G$ one can split the set of vertices $V$ into two disjoint subsets $U,W \subset V$ such ...

5
votes

1
answer

265
views

### Bijectively counting labeled trees by number of leaves

A rooted, labeled tree on $n$ vertices is a tree with vertex set $[n] := \{1,2,\ldots,n\}$ in which one vertex has been designated the root. A leaf of a rooted tree is a vertex $v$ for which either: $...

1
vote

0
answers

42
views

### When can infinite graphs be partitioned into trees of a given minimum size

Let $G=(V,E)$ be a graph with $0<\#V\leq \#\mathbb{N}$ and fix $n\leq \#V$. When can $G$ be partitioned into $(V_1,E_1),\dots,(V_m,E_m)$ where $V= \cup_i \, V_i$, $\#V_i\geq n$ and $E_i$ contains ...

1
vote

1
answer

74
views

### Stern-Brocot tree and subtree

Let $a(n)$ be A007306, denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range $[0,1]$).
Let $b(n)$ be A002487, Stern's diatomic series (or Stern-Brocot sequence): $b(0) = 0, ...

2
votes

0
answers

37
views

### Estimating the largest radius making each ball in a finite metric space into a tree

Motivation:
Let $n$ be a positive integer and $(X,d)$ be an $n$-point metric space. Clearly, $(X,d)$ need not be a metric tree (e.g. take for example the discrete metric on $\{0,1,2\}$.
Conversely, ...

7
votes

0
answers

287
views

### "Meritocratic" pyramid schemes

There have been a couple of times in my life when people from multi-level marketing organizations attempted to recruit me. I listened to what they had to say, and both times I did not get involved ...

6
votes

0
answers

271
views

### Power law correction factor in tree enumeration via naïve division

It is a theorem of Otter, building on fundamental work of Pólya, that the number of unlabeled trees on $n$ vertices is $\approx C \alpha^{n} n^{-5/2}$, where $C = 0.534\ldots$ and $\alpha = 2.955\...

15
votes

2
answers

1k
views

### Are hyperbolic spaces actually better for embedding trees than Euclidean spaces?

There is a folklore in the empirical computer-science literature that, given a tree $(X,d)$, one can find a bi-Lipschitz embedding into a hyperbolic space $\mathbb{H}^n$ and that $n$ is "much ...

2
votes

0
answers

104
views

### What classes of graphs result from $\overline{T}$?

I need help in characterizing the classes of graphs that results from taking the complementary of a tree, i.e., the graph that results from removing the edges of a tree from a complete graph. More ...

2
votes

1
answer

82
views

### Completing a tree to a 2-connected outerplanar graph

Let $T$ be a given (finite) tree.
Question 1: Is it always possible to add edges to $T$ to obtain a $2$-connected outerplanar supergraph $G$?
Question 2: If the answer to Question #1 is negative, can ...

1
vote

0
answers

61
views

### Partitioning antidirected trees with bounded degree, such that the graph induced by the partition is a constant antidirected tree

Given a partition of the vertices of a graph, we can define an auxiliary graph which conveys information about the edges between sets of the partition. This defines a graph with vertex set equal to ...

1
vote

1
answer

146
views

### Construct a rooted plane tree with nodes labelled

A rooted tree is a tree with a distinguished root node. When a rooted tree is embedded in a plane, a cyclic ordering is induced on the subtrees of the root. Such trees are called rooted plane trees.
...

3
votes

1
answer

122
views

### Probability calculation of rooted trees

Given a rooted tree $T_r$ (up to isomorphism), define the probability $P(T_r)$ as the probability of ending up with $T_r$ if one starts with a single (root) vertex and incrementally connects new ...

13
votes

1
answer

518
views

### Bijective proof of recurrence for rooted unlabeled trees

Would've been a better question for Christmas than Thanksgiving, but alas...
Let $t_n$ denote the number of rooted, unlabeled trees on $n$ vertices (OEIS A000081). These are the isomorphism classes of ...

1
vote

0
answers

82
views

### Varieties of trees with logarithmic degree function

I am interested in varieties of trees with a logarithmic degree function. I am currently looking at Bergeron, Flajolet, and Salvy's work "Varieties of increasing trees." They discuss exactly ...

0
votes

0
answers

65
views

### Perfectly balanced spanning trees

I call a spanning tree perfectly balanced if, after a two-coloring of the tree-graph's vertices
the two vertex sets that are defined by the assigned colors have equal cardinality and
the two vertex ...

0
votes

0
answers

23
views

### Limit behavior of MSTs edge sets under addition of weight doubling vertex potentials

Let $G(V,E)$ be a complete simple graph for which each of its edges has an associated weight.
The edge-set of every spanning tree of $G$ is trivially adjacent the $n$ vertices of $G$ and has $n-1$ ...

1
vote

0
answers

84
views

### cemetery tree $\delta$

Let $T_*$ be a tree on which the parent $e_*$ of the root is added and $x\in\mathbb{V}$ a vertex in the Ulam-Harris tree.
Then the tree $T_*^{\leq x}$ is defined as
\begin{cases}
\mathsf{T}_*\...

2
votes

1
answer

270
views

### Maximum number of leaf blocks in 3-regular (cubic) graph

The definition of block is
Block of $G$ is a maximal subgraph $G'$ of $G$ with no cut vertex of $G'$ itself.
Of course, there can exist many blocks in $G$.
In particular, isolated vertices, edges in ...

2
votes

2
answers

366
views

### Two independent spanning trees of $2$-connected graph

I want to prove the following statement:
Let $u$ be a vertex in a $2$-connected graph $G$. Then $G$ has two spanning trees such that for every vertex $v$, the $u,v$-paths in the trees are independent....

2
votes

1
answer

159
views

### Galton-Watson process: branching property

I am looking for the definition of the ‚branching property‘ of a Galton Watson process. Can someone give me an example about it?
It looks to me like an independence.
I have a branching processes book, ...

0
votes

1
answer

63
views

### Random walks on GW-trees (transformation)

Let $(X_n)_{n\in\mathbb{N}_0}$ be a biased Random Walk on Galton-Watson tree with $\lambda\in(\lambda_c,m)$.
How can I obtain the following equation:
$\sum_{k=0}^{n-1}\mathbb{E}_{e_*}[|X_{k+1}|-|X_k| \...

1
vote

1
answer

60
views

### Random walks on GW-trees (regeneration epochs/survival set)

Let $\Gamma_0,\Gamma_1,...$ be regeneration epochs.
If $(X_n)_{n \in \mathbb{N}}$ is a $\lambda$ biased random walk on a Galton-Watson tree, than the regeneration epochs are defined as:
$\Gamma_0:=\...

3
votes

0
answers

79
views

### If the girth of a $2k$-regular graph $G$ is larger than the diameter of a tree $T$ with $k$ edges, then $G$ is decomposed into copies of $T$

I want to prove that ‘If the girth of a $2k$-regular graph $G$ is larger than the diameter of a $k$-edge tree $T$, then $G$ is covered by edge-disjoint copies of $T$.’
I tried several ways to solve ...

1
vote

1
answer

193
views

### Random walks on Galton–Watson trees

I am working on a paper of Elie Aidekon : ‘Speed of the biased random walk on a Galton–Watson tree’ and have a question about one transformation in a proof:
\begin{align}
& 1+\frac{1}{1-\lambda}+\...

5
votes

2
answers

406
views

### About the maximum number of leaves adjacent to a vertex in a tree

Let $T$ be a finite tree graph with the set of vertices $V(T)$. For an arbitrary vertex $ v \in V(T)$, I define $l(v)$ to be the number of leaves connected to $v$.
In my study, I need to define the ...

1
vote

1
answer

96
views

### Empirical degree distribution of random $n$ vertices labeled rooted tree converges to Poisson distribution

I am reading Louigi's lecture note on random trees and graphs here. I get stuck on part (b), Exercise 1.2.3 on page 19, which says the following:
Let $T_n$ be uniformly drawn from $\mathcal{T}_n$, ...

5
votes

0
answers

74
views

### Finite trees with forests realizing all partitions

Removing interiors of some edges in a tree with $n$ vertices leaves a spanning-forest
with $k$ connected components (given by subtrees) having respectively $\lambda_1,\ldots,\lambda_k$
vertices. We ...