# Tag Info

8

This is more often stated in the form "if a tree $T$ is infinite and every node has only finitely many children then there exists an infinite path in $T$" (see König's Lemma). The infinite path may be constructed as follows: Let $x_0$ denote the root of $T$. Now $x_0$ has only finitely many children but $T$ is infinite so there must be at least one child of ...

8

A graph can be thought of as a pair $(V,E)$, where $V$ are the vertices and $E$ are the edges. An isomorphism between two graphs, $G_1 = (V_1,E_1)$ and $G_2=(V_2,E_2)$ means a function $f\colon V_1\to V_2$ that is bijective between the vertices (one-to-one and onto, so every vertex in $G_1$ is mapped to a vertex of $G_2$, and each vertex in $G_2$ is the ...

7

As others have pointed out, the transformation you're asking for is called the Hadamard transform (it essentially works like a discrete Fourier transform). While the "trivial" matrix multiplication takes $O(n^2)$ time, the structure of the matrix allows the computation to be done in $O(n\log n)$ time. However, it's less than like that this can be speeded up ...

7

Orient all edges towards the larger of the two subtrees obtained if one would remove the edge (if the two subtrees have equal size toss a coin). Now starting in an arbitrary node follow some edge in the oriented direction until this is no longer possible, in other words until all edges of the current node point towards it (it is obvious this terminates, ...

7

I don't know a way to make the proof of propositional compactness, for uncountable sets of formulas, look like a tree argument. But if you go back to how König's Lemma is usually proved and apply that argument to the particular tree that you described, then the resulting argument for propositional compactness generalizes quite directly, to the following ...

7

Here is a way to prove compactness for propositional logic in terms of trees. As Andreas mentions in the comments, the tree property for $\omega$ is not enough. Instead, we can use a two-cardinal variation of the tree property. If $\kappa$ is a regular cardinal and $\lambda \ge \kappa$, a $(\kappa,\lambda)$ tree $T$ is a set of $2$-valued functions whose ...

6

Here's one way to at least guess the growth rate. A random binary tree of size $n$ is the same thing (plus or minus one) as a random walk on the non-negative integers of length $n$ starting and ending at $0$, with the height of the tree corresponding to the farthest the walk goes from $0$. The order of magnitude of the height should behave like the order ...

6

The OP is in the correct direction. By Cayley's formula, the number of labeled trees on $n$ vertices is $n^{n-2}$. We will count the number of labelled trees in a different way and get the equality. Take a tree $T$ and an edge $e \in T$. Then $T \setminus \{ e \}$ contains two components, say of sizes $k$ and $n-k$. Also, each of the components is a tree ...

5

The Lambert function has the following Maclaurin series: $$-W(-x)=\sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k$$ (In some references, $-W(-x)$ is referred to as the "tree function", $T(x)$, as it is a generating function for rooted labeled trees.) This series can be derived through Lagrangian inversion. In particular, the coefficient of $x^k$ in the power ...

5

Notice that: $$\sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} \stackrel{k \to n+1-k}{=} \sum_{k=1}^n \frac{(n+1-k)^2}{n} \binom{n+k-2}{n-1} \stackrel{\binom{a}{b} = \binom{a}{a-b}}{=} \sum_{k=1}^n \frac{(n+1-k)^2}{n} \binom{n+k-2}{k-1} = \sum_{k=0}^{n} \frac{(n-k)^2}{n} \binom{n+k-1}{k}$$ This this nothing but a convolution of two sequences $a_{k} = ... 5 You need to check the following conditions: (i) The left subtree of a node contains only nodes with keys less than the node's key. (ii) The right subtree of a node contains only nodes with keys greater than the node's key. So let's do this for case one by looking at the values for the nodes we traverse until we either find 363 or until one of the ... 5 If this$Z \lt V + W$, then consider the the minimum weight spanning tree for which Z is attained. Let its weight according to v be V' and according to w be W'.$V' + W' \lt V + W$, so either V' < V or W' < W, which is not possible as V and W are the weights for the minimum spanning trees for v and w, respectively. 5 There's no need to consider the Laplacian. We can obtain this by a simple symmetry argument. Every edge of the complete graph is contained in a certain number of spanning trees. By symmetry, this number is the same for each edge, call it$k$. Let us now count the total number of edges in all spanning trees in two different ways. First, we know there are ... 5 To determine if a context free grammar is ambiguous is undecidable (there is no algorithm which will correctly say "yes" or "no" in a finite time for all grammars). This doesn't mean there aren't classes of grammars where an answer is possible. To prove a grammar ambiguous, you do as you outline: Find a string with two parses. To prove it unambiguous is ... 5 It should be$2^{k+1}-1$. The proof is as follows: In a full binary tree, you have 1 root, 2 sons of that root, 4 grandsons, 8 grand-grandsons and so on. So the total number of nodes is the sum of the geometric series: $$1+2+4+8+\dots +2^{k} = \frac{2^{k+1}-1}{2-1}=2^{k+1}-1$$ where$k$is the depth (i.e. for$k=0$we have 1 node). 5 Call the original tree$T_0$. Remove all the leaves of$T_0$to get a tree$T_1$. Then remove all the leaves of$T_1$to get$T_2$. After finitely many iterations, you get a tree$T_n$which is all leaves, and therefore consists of either a single vertex, or two vertices connected by an edge. Any automorphism$\sigma$of the original tree$T_0$must take ... 5 Let$n = pq$for two numbers$p,q \geq 3.$Consider the graph$B_{p,q}$obtained by taking two cycles of length$p$and$q$that share a common vertex. Then$t(B_{p,q}) = pq = n.$Hence for any$n$that has two divisors$\geq 2$you can find a graph satisfying your equality. Note that you can generalize this to any number of divisors of$n$as long as they ... 4 The one you called$\text{DC}_\kappa(2)$seems to be equivalent to the statement "every tree of height$\le \kappa$such that every branch of length$<\kappa$can be continued has a branch of length$\kappa$." This is also equivalent to the statement that every tree of height$\le \kappa$has a maximal branch. If every tree of height$\le \kappa$has a ... 4 There is indeed an ordinal interpretation of Friedman's block subsequence theorem; however, the associated ordinal is not between$\varepsilon_0$and$\Gamma_0$; it is$\omega^{\omega^\omega}$. More precisely, k-labelled sequences have ordinal$\omega^{\omega^{k-1}}$. Friedman's block subsequence theorem is provable in the theory$I\Sigma_3$but not the ... 4 This is not a solution, or even a useful hint, but perhaps these comments will be useful to someone. Let$t(n,h)$be the number of binary trees of height$h$having$n$nodes; if I understand correctly, you’re to find some sort of usable expression for$t(n,h)$. That appears to me to be a very hard problem. A few results are easy:$t(h+1,h)=2^h$, ... 4 A tree is a graph that is connected and does not contain any cycles. Since$T_1 \cap T_2$is a subgraph of both$T_1$and$T_2$, which are trees, it can obviously not contain cycles. What remains to be shown is that$T_1\cap T_2$is still connected. Fix two vertices$v_1, v_2$in$T_1\cap T_2$. Obviously, we then also have$v_1, v_2\in T_1$and$v_1, v_2\in ...

4

In answer to the first version of the question (between any $v$ and any $y$): ------------------------------------------------------< y is at the left, v is at the vee The answer to the second version of the question is yes. Suppose that $v$ were more than $\frac{D}{2}$ away from all leaves, where $D$ denotes the graph diameter. Pick two of the ...

4

There are situations where acyclicity is a very desirable phenomenon. For example, consider a "dependency graph", where the presence of the edge $A \to B$ means that you need $A$ to get $B$. Such graphs arise naturally in many contexts: In an adventure game, actions often have preconditions. For example, to enter the shed you might need to open the ...

4

Yes if you assume a group has a normal subgroup $Z$ of finite index which is infinite cyclic then it's much easier. If $Z$ is central, then a classical theorem shows that the derived subgroup is finite. So modding out by the derived subgroup, you get an abelian group, and eventually get that the group has a homomorphism onto $\mathbf{Z}$ (with finite kernel, ...

4

I incidentally came on this post. The OP was on the right path. He proved that $$T_n=\frac{n}{2}\sum_k\binom{n-2}{k-1}T_kT_{n-k}.$$ This is euqivalent to say $$\begin{eqnarray}2T_n&=&\sum_k(k+(n-k))\binom{n-2}{k-1}T_kT_{n-k}\\ ... 3 For each list, split it in two lists: one with numbers smaller than 363 and one with bigger. The first list should be sorted ascending, the other descending. That is because when you search in a BST you compare the node value to your query and get rid of the branch witch doesn't include your value. 925 911 912 -> bad 924 911 898; 220 244 258 362 -> good ... 3 Consider the space of lattice points (p,q) where 0 \leq p \leq q, q = 0, 1, \dots; the number of (shortest) paths in this space from (p,q) to (0,0) is the ballot number$$N(p,q) = \frac{q-p+1}{q+1} \cdot \binom{p+q}{p}; \quad N(0,0) =_D 1. Using this notation we have $N(n-k,n-1) = \frac{k}{n} \binom{2n-k-1}{n-1}$. The problem asks to show ...

3

The structure of the tree need not be the one described. And counting recipients by layers is not the most efficient or reliable way. We have $10000$ people sending letters, each to $5$ "new" people. On the assumption, unfortunately not entirely safe, that any letter sent is received, there are $50000$ recipients. Note that $9999$ of the people who send ...

3

There is no reason to believe that all the people that fail to send the letter onward are contained in the last level. I think your tree is putting more details into the problem than is necessary. 10,000 people sent a total of 50,000 letters. 9,999 letters were received by these 10,000; the remaining 40,001 letters were received by other people.

3

I think the easiest way it to regard this a knock-out competition with $n$ teams, each inner node is a match, and there is one winner. So there are $n-1$ teams to knock out and so $n-1$ nodes. Or you could do it by induction noting that replacing a pair of leaves and an inner node by a leaf reduces the number of inner nodes and leaves by 1, and that if ...

Only top voted, non community-wiki answers of a minimum length are eligible