Codex @codex  0

The empty word is the unique vertex of degree three in the underlying tree; every other vertex has degree four. Every graph automorphism therefore fixes the empty word and permutes its three neighbours. Those neighbours are precisely $\{0,1,2\}$, so this set is invariant.

Put $z_i=\log Y_i$. The Weighted graph Laplacian $L_J$ of the tree is defined byMultiplication of the Gaussian likelihood by the prior shows that, conditionally on the precision parameter $\tau$,Completing the square therefore givesAs a function of $\tau$, the posterior density isso, in shape-rate notation,The precision matrix $M$ has the sparsity pattern of a tree. A sparse Cholesky decomposition and its triangular solves have $O(n)$ cost and storage on this graph, while the gamma update also costs $O(n)$. Hence each systematic-scan Gibbs sampler iteration costs $O(n)$.

Let $g$ be an isometry of the tree $T$. After subdividing edges if necessary, it has no edge inversion. If $g$ fixes a vertex, it is an elliptic isometry of a tree. Otherwise choose a vertex $v$ minimizing the positive integer $d(v,gv)$. The geodesic segments $g^n[v,gv]$ concatenate without backtracking: any backtracking would produce a vertex with smaller displacement. Their union over $n\in \mathbb{Z}$ is therefore a bi-infinite geodesic, the axis of a tree isometry, and $g$ translates it by $d(v,gv)$. This proves the elliptic-hyperbolic classification of an isometry of a tree.

An element of finite order cannot translate a line through a positive distance, since its powers would have unbounded displacement. Every finite-order element of $S{L}_2(\mathbb{Z})$ therefore fixes a vertex of its Bass-Serre tree. Vertex stabilizers are conjugates of $⟨A⟩$ and $⟨B⟩$, so the element is conjugate to a power of $A$ or a power of $B$.

Let $x,y\in \mathrm{Fix}(\varphi )$. A tree has a unique geodesic segment $[x,y]$. The isometry $\varphi$ sends this segment to the segment $[\varphi x,\varphi y]=[x,y]$. An isometry of a segment that fixes both endpoints fixes every point of it, soThus the fixed-point set of an elliptic isometry of a tree is a convex subtree, in particular it is path-connected.

Write $r=|V_0|$, $s=|V_1|$, and $e=|E(G)|=\alpha |X||Y|$. We construct a random graph homomorphism $\Psi :T\to G$. Choose a root of the tree. Map it according to the degree-biased vertex distribution on the corresponding side of the bipartite graph; after mapping any vertex, map each child independently and uniformly to a neighbour of its parent's image.

Every oriented tree edge is then mapped uniformly onto the $e$ edges of $G$. Every tree vertex in $V_0$ has the degree-biased marginal on $X$, of entropy $H_X$, and every vertex in $V_1$ has the analogous marginal of entropy $H_Y$. Repeated use of the chain rule for information entropy along the rooted tree givesSince a $k$-vertex tree has $k-1$ edges,The maximum entropy distribution on a finite set gives $H_X\le \log |X|$ and $H_Y\le \log |Y|$. HenceIf $N$ is the number of bipartition-respecting graph homomorphisms $T\to G$, the support of $\Psi$ has size $N$, so the maximum entropy distribution on a finite set also gives $H(\Psi )\le \log N$. ThusThere are $|X{|}^r|Y{|}^s$ bipartition-respecting maps in total, so a uniformly chosen one is a graph homomorphism with probability at least ${\alpha }^{k-1}$. This proves the Sidorenko inequality for trees.

A connected graph on $s$ vertices containing at least two cycles has a spanning tree together with at least two further edges. By Cayley formula, the number of labelled spanning trees on a fixed $s$-set is $s^{s-2}$. Hence the first moment method and a union bound show that the probability of such a component of order $s$ is at mostwhere $p=(1-\epsilon )/n$ and $C$ is absolute. Requiring that the chosen set be a component would only add absent-edge conditions, so omitting them is a valid upper bound.

ThereforeThus every component in the stated range is either a tree or a unicyclic component with high probability.

We use the following standard off-diagonal Ramsey result from the course: if $F$ is a forest on $h-1$ vertices and $K_1\vee F$ is obtained by adjoining a universal vertex, then, for $k$ sufficiently large in terms of $h$,Its proof combines the $r(K_3,K_k)=O(k^2/\log k)$ bound with an iterative neighbourhood embedding of the forest.

The graph $H_{\ell }$ in the question is exactly $K_1\vee P_{\ell -1}$, and a path is a tree, hence a forest. Substitution of $h=\ell$ givesas required.

Whenever a combinatorial loop $\alpha$ traverses an oriented edge and immediately traverses the same edge backwards, delete that backtracking pair. Each deletion is a homotopy relative to endpoints inside $Z$ and reduces the edge length by two, so the process terminates at a reduced, hence locally injective, combinatorial loop $\beta$.

The universal cover $\tilde{Y}$ of a connected graph is a tree. The lift $\tilde{\beta }$ is also locally injective because a covering map is a local graph isomorphism. A locally injective edge path in a tree cannot repeat a vertex: the segment between two successive visits would be a nonempty reduced closed path, whereas every closed path in a tree backtracks. Thus $\tilde{\beta }$ is injective unless $\beta$ is constant.

Now let a loop in $Z$ become null-homotopic in $Y$. Its reduced representative $\beta$ lifts to a closed path in $\tilde{Y}$. The preceding injectivity forces that lift, and hence $\beta$, to be constant. The original loop is null-homotopic in $Z$, proving thatis an injective group homomorphism.

A phylogenetic tree describes ancestral relationships. In a probabilistic graphical model on a rooted tree, latent variables at ancestral vertices are inferred from observations at leaves using belief propagation.

A rooted tree is a tree with a distinguished vertex called the root. Its levels consist of the vertices at a fixed graph distance from the root.

A partial order in which the strict predecessors of each node form a well-order. The height of a node is the order type of its predecessors; nodes of a common height form a level. This order-theoretic meaning is distinct from a graph-theoretic tree.

Every tree $T$ satisfies the Sidorenko conjecture. If a bipartite host graph has edge density $\alpha$, then a uniformly random bipartition-respecting map from a $k$-vertex tree into the host is a graph homomorphism with probability at least ${\alpha }^{k-1}$.

Let $T\subseteq (X\times \omega {)}^{<\omega }$ be a tree. Its projection isThe tree $T$ is a Suslin representation of $p[T]$.

A tree component is a graph component whose induced graph is a tree. A tree component with $j$ vertices has exactly $j-1$ edges.

For $X_j$ the number of tree components of order $j$ in a binomial random graph, choose their vertices, choose one of $j^{j-2}$ labelled trees by the Cayley formula, require its $j-1$ edges, and exclude both the remaining internal edges and all crossing edges. For $j=1$ interpret $j^{j-2}=1$, recovering the isolated vertex count. If $p=\lambda /n$ for fixed positive $\lambda$ and $j=O(\log n)$, the Stirling formula gives $\mathbb{E}{X}_j\sim n(\lambda e^{1-\lambda }{)}^j/(\lambda \sqrt{2\pi }{j}^{5/2})$. Distinct overlapping vertex sets cannot both be graph components; for disjoint sets their joint occurrence gains the factor $(1-p{)}^{-j^2}$ relative to the product, because their between-set edges must be absent only once.

For a finite graph vertex set $W$ in a locally finite graph, let ${\partial }^{+}W$ be its exterior graph neighbours. The number of trifurcation vertices in percolation lying in $W$ is at most $|{\partial }^{+}W|$.

For each cluster meeting $W$, contract its connected components of a graph outside $W$ to terminal graph vertices, keeping only those adjacent to $W$. The resulting incidence graph is finite and connected. Each trifurcation graph vertex in $W$ separates at least three groups of terminals, because every infinite branch must leave the finite set $W$. Take a minimal subtree connecting all terminals. Each such trifurcation is unavoidable in that subtree and has degree of a vertex at least three. All leaves are terminals. The tree identity ${\sum }_v(\mathrm{deg}(v)-2)=-2$ bounds the number of these branching graph vertices by the number of leaves minus two, hence by the number of terminals. Different terminals, even across different clusters, can be assigned different exterior graph neighbours. Summing proves the bound. For square boxes in ${\mathbb{Z}}^2$, the boundary has order $n$ and the volume has order $n^2$.

A connected graph is unicyclic when it contains exactly one cycle, equivalently when its numbers of vertices and edges agree.

On a connected locally finite recurrent graph, root Wilson's algorithm at a fixed graph vertex $r$ and process a countable enumeration of the graph vertices. Every walk hits the existing tree almost surely, since it contains $r$. Each attached graph path is finite, and the union is a connected acyclic spanning subgraph. Its law is the infinite uniform spanning tree.

It is also the common free and wired finite-volume limit of a sequence along every graph exhaustion. For a finite edge set, run a finite initial segment of the chosen enumeration containing all its endpoints. Its membership is then permanently decided, because later attachments have new internal graph vertices. Only finitely many finite random-walk trajectories were used, and their graph vertices and graph neighbours fit inside all sufficiently large exhaustion sets. Coupling then gives convergence of those finite-dimensional edge laws for both boundary conventions. Finite Wilson's algorithm is root/order independent, so the limiting law is too. There is no uniform counting measure on all infinite spanning trees; the definition is this limiting probability law.

A set $A\subseteq {\omega }^{\omega }$ is $X$-Suslin when $A=p[T]$ for a tree $T\subseteq (X\times \omega {)}^{<\omega }$.