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.
76
questions with no upvoted or accepted answers
17
votes
0
answers
405
views
Is the Frog game solvable in the root of a full binary tree?
This is a cross-post from math.stackexchange.com$^{[1]}$, since the bounty there didn't lead to any new insights.
For reference,
The Frog game is the generalization of the Frog Jumping (see it on ...
12
votes
0
answers
327
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 ...
9
votes
0
answers
155
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 ...
9
votes
0
answers
492
views
A separation property of graphs of bounded tree-width
The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)
Let $T$ be a tree and $r, m$ non-...
9
votes
0
answers
289
views
Weighted sum of the Simsun (Andre) permutations
Let $ c_{n,k} $ be the Simsun permutations$^1$ defined by the following relations: $\displaystyle c_{n,0} = 1, \hspace{0.1cm} (n \ge 1);$
$$ c_{n,k} = (k+1) c_{n-1,k} +(n-2k+1) c_{n-1,k-1}, \hspace{0....
8
votes
0
answers
401
views
Parity of oriented rooted trees
Suppose we have a planar graf with vertices $v_o, \ldots, v_n$, where $n$ is even such that if we checkerboard-color regions in the complement, then the black regions are $n$ (non-degenerated) ...
7
votes
0
answers
234
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 ...
7
votes
0
answers
295
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 ...
7
votes
0
answers
149
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 ...
6
votes
0
answers
274
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\...
6
votes
0
answers
82
views
Distributions of "sequential" binomials
I have come across the following stochastic process which seems very elementary, although I do not know any appropriate terminology for it; I greatly appreciate any suggestions!
Suppose I am given ...
5
votes
0
answers
76
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 ...
5
votes
0
answers
177
views
Examples of non-uniform lattices in products of trees
Consider a product of two locally-finite, infinite, unimodular trees $X=T_1\times T_2$. Assume that both ${\rm Aut}(T_1)$ and ${\rm Aut}(T_2)$ are not discrete.
So as a vague general question, what ...
5
votes
0
answers
96
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 ...
5
votes
0
answers
141
views
Growth in families of trees
I'm hoping that the question below is simple thermodynamic formalism, but I can't quite make it work. Any help would be very welcome.
Let $\Sigma:=\{0,1\}^{\mathbb N}$ and let $\Sigma^*$ be the set ...
4
votes
0
answers
513
views
Is the integer factorization into prime numbers normally distributed?
Edit:
Sorry, for the inconvenience: I have edited the question, since there was a misconception in my thinking.
Let $P_1(n) := 1$ if $n=1$ and $\max_{q\mid n, \text{ } q\text{ prime}} q$ otherwise, ...
4
votes
0
answers
139
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 ...
4
votes
0
answers
299
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 ...
4
votes
0
answers
156
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 ...
4
votes
0
answers
936
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 ...
3
votes
0
answers
86
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 ...
3
votes
0
answers
107
views
Are all intermediate growth branch groups just-infinite?
Are all branch groups of intermediate growth just-infinite? I can't seem to find an answer to this one way or another; the question is motivated by the fact all examples of intermediate growth branch ...
3
votes
0
answers
72
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 ...
3
votes
0
answers
336
views
Finding many disjoint sub-trees with many leaves
Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
3
votes
0
answers
134
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 ...
3
votes
0
answers
1k
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 ...
2
votes
0
answers
102
views
Existence of trees with height $\kappa$, every level has at most size $\lambda$ and has at least $\lambda^{+}$ maximal branches
Definitions A tree means a set-theoretic tree, that is a poset $(T,<)$ so that for each $x\in T$, the set $\{y\in T\mid y<x\}$ is well-ordered.
A $\kappa$-Kurepa tree is a tree of height $\kappa$...
2
votes
0
answers
46
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\...
2
votes
0
answers
61
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 ...
2
votes
0
answers
115
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 ...
2
votes
0
answers
128
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
0
answers
38
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, ...
2
votes
0
answers
105
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
0
answers
129
views
Decomposing a metric tree as a union of rooted (or "centered") trees
Suppose $G$ is a finite metric tree whose set of leaves is $A=\{v_1, \ldots, v_n\}$. Consider the function $G\to \mathbb R_+$ that assigns to a point $x$ the distance from $x$ to $A$, denoted $d(x, A)$...
2
votes
0
answers
60
views
Is there a name for a tree with all leaf vertices identified with each other?
Is there a name for those graphs that can be formed by taking a tree and identifying all the vertices of degree 1 (leaves) with each other?
Or, if I understand correctly, an equivalent definition may ...
2
votes
0
answers
65
views
Infinite trees whose spectrum has more than 3 connected components
I was wondering whether there exists any infinite tree $T$ such that the action of $\mathit{Aut}(T)$ on the set of vertices $V=V(T)$ has finitely many orbits, and whose spectrum $\sigma(T)$ has ...
2
votes
0
answers
228
views
Finite index subgroup of HNN extension
Let $GX$ be a tree group (a right-angled Artin group such that the graph is a tree), such that not all the subgroups of $GX$ are necessarily RAAGs, so the length of the tree is greater or equal than $...
2
votes
0
answers
55
views
Admissible (unitary) spherical representation $sl(2,Q_p)$. Does dimension fixed point vector increase proportional index
I am using terminology of Cartier's Harmonic analysis on trees. Take $\pi$ be one of the irreducible principal or complementary (unitary) spehrical series of $Sl(2, Q_p)$. Let $K$ be the maximal ...
2
votes
0
answers
84
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 ...
2
votes
0
answers
145
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.
...
2
votes
0
answers
109
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 ...
2
votes
0
answers
99
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 ...
2
votes
0
answers
81
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^{\...
2
votes
0
answers
103
views
Is there a name for this variant of the MST and the TSP?
Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as ...
2
votes
0
answers
52
views
LDP respectively almost sure convergence in the context of randomly weighted trees
I am currently working on the following Problem:
Imagine you are given a $d$-ary tree $T_d$, which means an infinite tree with one vertex $x_0$ on top and in which each vertex has $d$ children.
Next,...
2
votes
0
answers
184
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 ...
1
vote
0
answers
79
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 ...
1
vote
0
answers
67
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 ...
1
vote
0
answers
117
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
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 (...