We study two models of discrete height functions, that is, models of random integer-valued functions on the vertices of a tree. First, we consider the random homomorphism model, in which neighbours must have a height difference of exactly one. The local law is uniform by definition. We prove that the height variance of this model is bounded, uniformly over all boundary conditions (both in terms of location and boundary heights). This implies a strong notion of localisation, uniformly over all extremal Gibbs measures of the system. For the second model, we consider directed trees, in which each vertex has exactly one parent and at least two children. We consider the locally uniform law on height functions which are monotone, that is, such that the height of the parent vertex is always at least the height of the child vertex. We provide a complete classification of all extremal gradient Gibbs measures, and describe exactly the localisation-delocalisation transition for this model. Typical extremal gradient Gibbs measures are localised also in this case. Localisation in both models is consistent with the observation that the Gaussian free field is localised on trees, which is an immediate consequence of transience of the random walk.

We show that the diameter of a uniformly drawn spanning tree of a simple connected graph on n vertices with minimal degree linear in n is typically of order $\sqrt{n}$ . A byproduct of our proof, which is of independent interest, is that on such graphs the Cheeger constant and the spectral gap are comparable.

A self-avoiding polygon is a lattice polygon consisting of a closed self-avoiding walk on a square lattice. Surprisingly little is known rigorously about the enumeration of self-avoiding polygons, although there are numerous conjectures that are believed to be true and strongly supported by numerical simulations. As an analogous problemto this study, we considermultiple self-avoiding polygons in a confined region as a model for multiple ring polymers in physics. We find rigorous lower and upper bounds for the number ${{p}_{m\times n}}$ of distinct multiple self-avoiding polygons in the $m\,\times \,n$ rectangular grid on the square lattice. For $m\,=\,2,\,{{p}_{2\times n}}\,=\,{{2}^{n-1}}\,-1$. And for integers $m,\,n\,\ge \,3$,

$${{2}^{m+n-3}}\left( \frac{17}{10} \right){{\,}^{\left( m-2 \right)\left( n-2 \right)}}\,\le \,{{p}_{m\times n}}\,\le \,{{2}^{m+n-3}}\left( \frac{31}{16} \right){{\,}^{\left( m-2 \right)\left( n-2 \right)}}.$$

A cutset is a non-empty finite subset of ℤd which is both connected and co-connected. A cutset is odd if its vertex boundary lies in the odd bipartition class of ℤd. Peled [18] suggested that the number of odd cutsets which contain the origin and have n boundary edges may be of order eΘ(n/d) as d → ∞, much smaller than the number of general cutsets, which was shown by Lebowitz and Mazel [15] to be of order dΘ(n/d). In this paper, we verify this by showing that the number of such odd cutsets is (2+o(1))n/2d.

We show that the diameter diam(Gn) of a random labelled connected planar graph with n vertices is equal to n1/4+o(1), in probability. More precisely, there exists a constant c > 0 such that

$$ P(\D(G_n)\in(n^{1/4-\e},n^{1/4+\e}))\geq 1-\exp(-n^{c\e}) $$

For an $N$-step self-avoiding walk on the hypercubic lattice ${{Z}^{d}}$, we prove that the meansquare end-to-end distance is at least ${{N}^{4/(3d)}}$ times a constant. This implies that the associated critical exponent $v$ is at least $2/(3d)$, assuming that $v$ exists.

This work studies the typical behaviour of random integer-valued Lipschitz functions on expander graphs with sufficiently good expansion. We consider two families of functions: M-Lipschitz functions (functions which change by at most M along edges) and integer-homomorphisms (functions which change by exactly 1 along edges). We prove that such functions typically exhibit very small fluctuations. For instance, we show that a uniformly chosen M-Lipschitz function takes only M+1 values on most of the graph, with a double exponential decay for the probability of taking other values.

Consider an independent site percolation model on Z d , with parameter p ∈ (0, 1), where all long-range connections in the axis directions are allowed. In this work we show that, given any parameter p, there exists an integer K(p) such that all binary sequences (words) ξ ∈ {0, 1} N can be seen simultaneously, almost surely, even if all connections with length larger than K(p) are suppressed. We also show some results concerning how K(p) should scale with p as p goes to 0. Related results are also obtained for the question of whether or not almost all words are seen.

We study a continuous-time stochastic process on strings made of two types of particle, whose dynamics mimic the behaviour of microtubules in a living cell; namely, the strings evolve via a competition between (local) growth/shrinking as well as (global) hydrolysis processes. We give a complete characterization of the phase diagram of the model, and derive several criteria of the transient and recurrent regimes for the underlying stochastic process.

Consider the single-server queue with an infinite buffer and a first-in–first-out discipline, either of type M/M/1 or Geom/Geom/1. Denote by 𝒜 the arrival process and by s the services. Assume the stability condition to be satisfied. Denote by 𝒟 the departure process in equilibrium and by r the time spent by the customers at the very back of the queue. We prove that (𝒟, r) has the same law as (𝒜, s), which is an extension of the classical Burke theorem. In fact, r can be viewed as the sequence of departures from a dual storage model. This duality between the two models also appears when studying the transient behaviour of a tandem by means of the Robinson–Schensted–Knuth algorithm: the first and last rows of the resulting semistandard Young tableau are respectively the last instant of departure from the queue and the total number of departures from the store.

For a given k ≥ 1, subintervals of a given interval [0, X] arrive at random and are accepted (allocated) so long as they overlap fewer than k subintervals already accepted. Subintervals not accepted are cleared, while accepted subintervals remain allocated for random retention times before they are released and made available to subsequent arrivals. Thus, the system operates as a generalized many-server queue under a loss protocol. We study a discretized version of this model that appears in reference theories for a number of applications, including communication networks, surface adsorption-desorption processes, and reservation systems. Our primary interest is in steady-state estimates of the vacant space, i.e. the total length of available subintervals kX - ∑ℓ i , where the ℓ i are the lengths of the subintervals currently allocated. We obtain explicit results for k = 1 and for general k with all subinterval lengths equal to 2, the classical dimer case of chemical applications. Our focus is on the asymptotic regime of large retention times.

We use the lace expansion to analyse networks of mutually-avoiding self-avoiding walks, having the topology of a graph. The networks are defined in terms of spread-out self-avoiding walks that are permitted to take large steps. We study the asymptotic behaviour of networks in the limit of widely separated network branch points, and prove Gaussian behaviour for sufficiently spread-out networks on ${{\mathbb{Z}}^{d}}$ in dimensions $d\,>\,4$.

We study a one-dimensional supercritical branching random walk in a non-i.i.d. random environment, which considers both the branching mechanism and the step transition. This random environment is constructed using a recurrent Markov chain on a finite or countable state space. Criteria of (strong) recurrence and transience are presented for this model.

We introduce and study a novel type of first-passage percolation problem on where the associated first-passage time measures the density of interface between two types of sites. If the types, designated + and –, are independently assigned their values with probability p and (1 — p) respectively, we show that the density of interface is non-zero provided that both species are subcritical with regard to percolation, i.e. pc > p > 1 – pc. Furthermore, we show that as p ↑ pc or p ↓ (1 – pc), the interface density vanishes with scaling behavior identical to the correlation length of the site percolation problem.