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
Filter by
Sorted by
Tagged with
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 ...
Vepir's user avatar
  • 591
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 ...
Gil Kalai's user avatar
  • 24.2k
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 ...
Gordon Royle's user avatar
  • 12.3k
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-...
monkeymaths's user avatar
  • 1,169
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....
user avatar
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) ...
user avatar
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 ...
Peter Kropholler's user avatar
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 ...
Favst's user avatar
  • 1,985
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 ...
Jing Zhang's user avatar
  • 3,138
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\...
Sam Hopkins's user avatar
  • 22.7k
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 ...
Tom Solberg's user avatar
  • 3,929
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 ...
Roland Bacher's user avatar
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 ...
Sam Hughes's user avatar
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 ...
Tom Solberg's user avatar
  • 3,929
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 ...
Tom Kempton's user avatar
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, ...
mathoverflowUser's user avatar
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 ...
MH.Fakharan's user avatar
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 ...
Desiderius Severus's user avatar
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 ...
user43932's user avatar
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 ...
Koundinya Vajjha's user avatar
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 ...
okw1124's user avatar
  • 331
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 ...
Thomas Meyer's user avatar
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 ...
Mathieu Baillif's user avatar
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$ ...
Or Meir's user avatar
  • 419
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 ...
Simon Smith's user avatar
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 ...
Zomulgustar's user avatar
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$...
George Marangelis's user avatar
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\...
pyridoxal_trigeminus's user avatar
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 ...
Timothy_G's user avatar
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 ...
Naysh's user avatar
  • 455
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 ...
fyo's user avatar
  • 51
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, ...
ABIM's user avatar
  • 5,019
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 ...
Lluís Alemany-Puig's user avatar
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)$...
Gregory Arone's user avatar
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 ...
Andrew Moylan's user avatar
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 ...
Maurizio Moreschi's user avatar
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 $...
J.L.'s user avatar
  • 321
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 ...
Florin Radulescu's user avatar
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 ...
Tobias Johnson's user avatar
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. ...
James Hanson's user avatar
  • 10.3k
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 ...
Daniel Alejandro Jaume's user avatar
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 ...
eagle34's user avatar
  • 161
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^{\...
user56097's user avatar
  • 402
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 ...
Tom Solberg's user avatar
  • 3,929
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,...
ssbm's user avatar
  • 21
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 ...
Val K's user avatar
  • 355
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 ...
CWC's user avatar
  • 359
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 ...
Peter Gerdes's user avatar
  • 2,551
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 $...
Vepir's user avatar
  • 591
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 (...
Hemraj Raikwar's user avatar