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.
230
questions
2
votes
0
answers
56
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 ...
- 193
9
votes
2
answers
1k
views
Terminology about trees
In set theory, a tree is usually defined as a partial order such that the set of elements below any given one is well-ordered. I am interested in the class of partial orders $P$ such that for every $...
- 18.1k
6
votes
0
answers
85
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 ...
- 3,929
8
votes
1
answer
767
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 ...
- 38.2k
3
votes
1
answer
196
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 ...
- 5,380
10
votes
2
answers
404
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]$.
...
- 5,380
1
vote
1
answer
364
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 : \...
- 629
7
votes
1
answer
532
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$ ...
- 383
11
votes
3
answers
402
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 ...
- 1,169
9
votes
0
answers
157
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 ...
- 12.3k
1
vote
0
answers
44
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 ...
- 221
6
votes
1
answer
198
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 ...
- 19.4k
1
vote
0
answers
47
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{ ...
- 193
7
votes
1
answer
495
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,\...
- 14.5k
1
vote
0
answers
47
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,...
- 16.7k
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 ...
- 1,817
7
votes
1
answer
700
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$...
- 3,929
2
votes
2
answers
481
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 \...
- 221
3
votes
1
answer
158
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 ...
- 221
5
votes
2
answers
322
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)=\...
- 371
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 ...
- 221
1
vote
1
answer
134
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 ...
- 195
3
votes
2
answers
207
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 ...
- 419
1
vote
0
answers
102
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,380
5
votes
1
answer
406
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$ ...
- 5,831
7
votes
0
answers
150
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,138
4
votes
1
answer
656
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,380
6
votes
2
answers
433
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 ...
- 3,680
9
votes
1
answer
569
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 $...
- 24.2k
0
votes
1
answer
179
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 ...
- 209
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 ...
- 24.2k
7
votes
1
answer
219
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$, $\...
- 209
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 ...
7
votes
1
answer
378
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$ ...
- 1,469
4
votes
0
answers
301
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 ...
- 5,314
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.
...
- 10.3k
10
votes
2
answers
1k
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\...
- 43.7k
8
votes
1
answer
337
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 ...
- 78.6k
7
votes
1
answer
404
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)...
- 4,435
3
votes
1
answer
318
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 ...
- 41
2
votes
2
answers
380
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 ...
- 375
12
votes
1
answer
422
views
Tree-width of a union of two trees
Is it possible to unite two $n$-vertex trees such that the resulting graph has bounded tree-width?
Formally, does there exists a constant $k$ such that given two $n$-vertex trees $T_1$ and $T_2$ ...
- 655
2
votes
1
answer
76
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 ...
- 155
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 ...
1
vote
0
answers
68
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
$$
\...
- 43
0
votes
1
answer
570
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).
- 1
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 ...
- 3,929
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 ...
- 161
1
vote
1
answer
181
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 ...
- 228
0
votes
0
answers
96
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{...
- 228