17
votes
Accepted
Is there a natural relationship between OEIS A127670 and Cayley's tree formula?
Yes there is a connection. While $n^{n-2}$ counts the number of vertex labeled trees on $n$ vertices, the expression $2^n(n+1)^{n-2}$ counts the number of edge labeled trees on $n$ edges. There is a ...
- 85.5k
17
votes
Accepted
How does the number of trees on $n$ vertices *up to isomorphism* grow as $n \to \infty$?
For Q1 the answer is known to be $\sim C_1C_2^n n^{-5/2} $ for $C_1\approx 0.5349496061...$ and $C_2\approx 2.9955765856...$. This can be found in Flajolet and Sedgewick's "Analytic Combinatorics&...
- 85.5k
16
votes
Groups acting on trees
Yes.
You're assuming more than what's necessary.
For an isometric group action on a Gromov-hyperbolic space, you have 5 possibilities (Gromov's classification):
(a) bounded orbits
(b) horocyclic (...
- 63.9k
15
votes
Accepted
History of deletion-contraction formula
This seems to have first been observed in
Brooks, R.L.; Smith, C.A.B.; Stone, A.H.; Tutte, W.T., The dissection of rectangles into squares, Duke Math. J. 7, 312-340 (1940). ZBL0024.16501.
See ...
- 68.8k
15
votes
Accepted
Göbel's correspondance between rooted trees and natural numbers
(I see this in the comments, too, but to ensure this has an actual answer...)
Here are the first fifteen natural numbers after drawing an individual line segment (edge and node) beneath the root:
As ...
- 7,831
12
votes
Accepted
A combinatorial interpretation for $n$-ary trees for negative $n$
Here's an explanation of the combinatorial meaning of $T_{-n}(x)$.
The combinatorial interpretation $T_n(x)$ is that it counts $n$-ary trees. More precisely, it counts ordered trees in which every ...
- 17k
12
votes
Accepted
Action of braid groups on regular trees
In the article A group theoretic criterion for property FA, Culler and Vogtmann notice that
for $n \geq 5$, the braid group $B_n$ has property $A \mathbb{R}$,
meaning that every non-trivial (i.e. ...
- 8,401
11
votes
A permutation problem
A simple brute-force of trees yields a counter-example with $n = 7$. Let $\{a_1, \ldots, a_7\} = [7]$, $T$ be a path of four vertices $v_1, v_2, v_3, v_4$, with $v_4$ adjacent to $v_5, v_6, v_7$. If ...
- 5,590
11
votes
Terminology about trees
They are also called trees.
In that terminology, trees of your first kind are known as the well-founded trees, since they are trees where the tree order is well-founded (and well-founded linear ...
- 236k
10
votes
Accepted
Destroying Suslin, nothing special
Chapter IX of Proper and Improper Forcing addresses this issue.
Shelah proves that Souslin's Hypothesis does not imply every Aronszajn tree is special, and he does this by investigating weak notions ...
- 7,125
10
votes
A tree with prime vertices
Not an answer, just a drawing of the tree including the
OP's $2 \rightarrow 191$ path:
- 151k
10
votes
Accepted
Counting with trees
Let me complete Sam Hopkins' answer.
The expression on the left is
$$
\Psi\left(\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j x_j^{i_j+1}\right)\\
=\sum_{i_1+\dots+i_{n+1}=n-1}{...
- 23.7k
9
votes
Almost graceful tree conjecture
I know no reference, but here is an easy way of achieving $|D|\geq\lceil n/2\rceil$ (for $n\geq 2$, surely).
The vertices of every tree can be decomposed into stars (i.e., graphs of te form $K_{1,d}$ ...
- 23.7k
9
votes
First inaccessible Suslin trees in L, an interesting detail
This will always be true. That is, I claim that forcing with a $\kappa$-Suslin tree always preserves all smaller cardinals, and indeed, preserves all cardinals and cofinalities.
Theorem. Forcing with ...
- 236k
8
votes
Accepted
Spanning $k$-trees
Regarding the question 1a, Bern showed that checking existence of a spanning $k$-tree in a graph is NP-complete for any fixed $k \geq 2$ (also see another, more accessible relevant paper by Cai and ...
- 5,590
8
votes
Accepted
Growth rate of longest sequence of strings where no string is a subsequence of a later one
I suppose it's a good idea to turn my comment into an answer.
The function $STR$ is basically the function $F$ defined by Friedman in this paper (more precisely, it's easy to show $STR(k)=F(k-1)+1$). ...
- 28.2k
8
votes
History of deletion-contraction formula
Not exactly a reference, but I found some discussion of this formula in Bill Tutte's graph-theoretic memoirs, Graph Theory as I Have Known it (Oxford, 1998). In Chapter 5 ("Algebra in Graph ...
- 3,393
7
votes
Accepted
Chromatic number of square of a tree
The particular case of the square of a tree is easy to handle by producing a greedy $(\Delta+1)$-coloring starting from a root vertex and extending. However, much stronger results are known:
The $k$-...
- 85.5k
7
votes
Gromov hyperbolicity constant vs. Gromov-Hausdorff distance to a tree
Just to remove this question from the un-answered list. First of all, if $d_{GH}(X,Y)\le \epsilon$ then there is a $(1,2\epsilon)$-quasi-isometry $X\to Y$.
See for instance
Burago, D.; Burago, Yu.; ...
- 12.2k
7
votes
Accepted
Are hyperbolic spaces actually better for embedding trees than Euclidean spaces?
I am not sure if the following paper answers your question. The abstract suggests so, but it is written in a computer science style that is less transparent to me in terms of stating a precise theorem....
- 86
7
votes
A combinatorial interpretation for $n$-ary trees for negative $n$
Added Apr. 23, 2023: More interpretations of these sequences of numbers are provided in my blog post "Interpretations of the (−m)−Fuss-Narayana numbers for m>0".
Added Apr. 10, 2023: (a ...
- 10.5k
7
votes
Accepted
Thick Canadian trees
$\newcommand{\Add}{\operatorname{Add}}$Start with a model $V$ satisfying $GCH$ (or just $2^{\omega}=\omega_1$ and $2^{\omega_1}=\omega_2$). Force over $V$ with the product $\Add(\omega,\omega_2)\times ...
- 1,799
7
votes
Counting with trees
Here's a start. Your claim is equivalent to (and easier to understand as)
$$ \sum_{T} \prod_{i=1}^{n+1} d_i(T)! = n! \, \frac{1}{2n+1}\binom{3n}{n}$$
where the sum is over all labeled trees $T$ on ...
- 24.2k
7
votes
Accepted
Matrix-tree theorem for inverse matrices
There is a formula as a sum of forests, i.e., collections of trees, for arbitrary minors of any size and row/column selection, for arbitrary matrices. So it can be applied for the numerator and the ...
6
votes
Accepted
Counting some binary trees with lots of extra stucture
I was able to find an interesting generalization of your formula, but I'm having trouble finding a reference in the literature.
Let's call a 0-1-2 tree, a rooted tree where every vertex can have no ...
- 85.5k
6
votes
Accepted
Number of independent sets of a random tree
The exact average number of independent sets in a random labelled tree of $n$ vertices is
$$ E_n = \sum_{k=0}^{n-1} \binom{n}{k} n^{1-k} (n-k)^{k-1}. $$
To prove this, use the Matrix Tree Theorem (or ...
- 37.7k
6
votes
Accepted
Bijective proof of formula for rooted binary forests
I think the following might do the trick:
Erdös, Péter L., A new bijection on rooted forests, Discrete Math. 111, No.1-3, 179-188 (1993). ZBL0785.05049.
- 5,792
6
votes
Asymptotics of unrooted labeled forests
The idea in the book by Flajolet-Sedgewick is to use singularity analysis. The generating function $F(z)=\exp(U(z))$ with $U=T-T^2/2$ inherits the dominant singularity $e^{-1}$ of $T(z)=-W(-z)$, where ...
- 361
6
votes
Accepted
Quotient graph of a tree
Yes, if $G$ is connected (and non-empty for simplicity).
Choose a vertex $v\in V(G)$. We define a tree $T$ in which the vertices are all the paths in $G$ that start in $v$ (including the path of ...
- 13.6k
6
votes
Accepted
Tree property at weak inaccessibles
In his paper Boolean extensions which efface the Mahlo property William Boos proves the following consistency result:
Theorem. Assume GCH holds and $\kappa$ is weakly compact. Then there exists a ...
- 32.1k
Only top scored, non community-wiki answers of a minimum length are eligible