When normal and mis`{e}re games are played on bi-type binary Galton-Watson trees (with vertices coloured blue or red and each having either no child or precisely $2$ children), with one player allowed to move along monochromatic edges and the other a
long non-monochromatic edges, the draw probabilities equal $0$ unless every vertex gives birth to one blue and one red child. On bi-type Poisson trees where each vertex gives birth to Poisson$(lambda)$ offspring in total, the draw probabilities approach $1$ as $lambda rightarrow infty$. We study such emph{nove
This paper studies the regular stochastic block model comprising emph{several} communities: each of the $k$ non-overlapping communities, for $k geqslant 3$, possesses $n$ vertices, each of which has total degree $d$. The values of the intra-cluster d
egrees (i.e. the number of neighbours of a vertex inside the cluster it belongs to) and the inter-cluster degrees (i.e. the number of neighbours of a vertex inside a cluster different from its own) are allowed to vary across clusters. We discuss two main results: the first compares the probability measure induced by our model with the uniform measure on the space of $d$-regular graphs on $kn$ vertices, and the second establishes that the clusters, under rather weak assumptions, are unique asymptotically almost surely as $n rightarrow infty$.
A coupling of random walkers on the same finite graph, who take turns sequentially, is said to be an avoidance coupling if the walkers never collide. Previous studies of these processes have focused almost exclusively on complete graphs, in particula
r how many walkers an avoidance coupling can include. For other graphs, apart from special cases, it has been unsettled whether even two non-colliding simple random walkers can be coupled. In this article, we construct such a coupling on (i) any $d$-regular graph avoiding a fixed subgraph depending on $d$; and (ii) any square-free graph with minimum degree at least three. A corollary of the first result is that a uniformly random regular graph on $n$ vertices admits an avoidance coupling with high probability.
We consider the abelian stochastic sandpile model. In this model, a site is deemed unstable when it contains more than one particle. Each unstable site, independently, is toppled at rate $1$, sending two of its particles to neighbouring sites chosen
independently. We show that when the initial average density is less than $1/2$, the system locally fixates almost surely. We achieve this bound by analysing the parity of the total number of times each site is visited by a large number of particles under the sandpile dynamics.
For any fixed positive integer $k$, let $alpha_{k}$ denote the smallest $alpha in (0,1)$ such that the random graph sequence $left{Gleft(n, n^{-alpha}right)right}$ does not satisfy the zero-one law for the set $mathcal{E}_{k}$ of all existential firs
t order sentences that are of quantifier depth at most $k$. This paper finds upper and lower bounds on $alpha_{k}$, showing that as $k rightarrow infty$, we have $alpha_{k} = left(k - 2 - t(k)right)^{-1}$ for some function $t(k) = Theta(k^{-2})$. We also establish the precise value of $alpha_{k}$ when $k = 4$.
Alternating quantifier depth is a natural measure of difficulty required to express first order logical sentences. We define a sequence of first order properties on rooted, locally finite trees in a recursive manner, and provide rigorous arguments fo
r finding the alternating quantifier depth of each property in the sequence, using Ehrenfeucht-Fra{i}ss{e} games.
Let $mathcal{B}$ be the set of rooted trees containing an infinite binary subtree starting at the root. This set satisfies the metaproperty that a tree belongs to it if and only if its root has children $u$ and $v$ such that the subtrees rooted at $u
$ and $v$ belong to it. Let $p$ be the probability that a Galton-Watson tree falls in $mathcal{B}$. The metaproperty makes $p$ satisfy a fixed-point equation, which can have multiple solutions. One of these solutions is $p$, but what is the meaning of the others? In particular, are they probabilities of the Galton-Watson tree falling into other sets satisfying the same metaproperty? We create a framework for posing questions of this sort, and we classify solutions to fixed-point equations according to whether they admit probabilistic interpretations. Our proofs use spine decompositions of Galton-Watson trees and the analysis of Boolean functions.
A well-known result of Shelah and Spencer tells us that the almost sure theory for first order language on the random graph sequence $left{G(n, cn^{-1})right}$ is not complete. This paper proposes and proves what the complete set of completions of th
e almost sure theory for $left{G(n, c n^{-1})right}$ should be. The almost sure theory $T$ consists of two sentence groups: the first states that all the components are trees or unicyclic components, and the second states that, given any $k in mathbb{N}$ and any finite tree $t$, there are at least $k$ components isomorphic to $t$. We define a $k$-completion of $T$ to be a first order property $A$, such that if $T + A$ holds for a graph, we can fully describe the first order sentences of quantifier depth $leq k$ that hold for that graph. We show that a $k$-completion $A$ specifies the numbers, up to cutoff $k$, of the (finitely many) unicyclic component types of given parameters (that only depend on $k$) that the graph contains. A complete set of $k$-completions is then the finite collection of all possible $k$-completions.
We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the othe
r hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton-Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).
Consider a statistical physical model on the $d$-regular infinite tree $T_{d}$ described by a set of interactions $Phi$. Let ${G_{n}}$ be a sequence of finite graphs with vertex sets $V_n$ that locally converge to $T_{d}$. From $Phi$ one can construc
t a sequence of corresponding models on the graphs $G_n$. Let ${mu_n}$ be the resulting Gibbs measures. Here we assume that ${mu_{n}}$ converges to some limiting Gibbs measure $mu$ on $T_{d}$ in the local weak$^*$ sense, and study the consequences of this convergence for the specific entropies $|V_n|^{-1}H(mu_n)$. We show that the limit supremum of $|V_n|^{-1}H(mu_n)$ is bounded above by the emph{percolative entropy} $H_{perc}(mu)$, a function of $mu$ itself, and that $|V_n|^{-1}H(mu_n)$ actually converges to $H_{perc}(mu)$ in case $Phi$ exhibits strong spatial mixing on $T_d$. We discuss a few examples of well-known models for which the latter result holds in the high temperature regime.
