Search

The gossip problem (telephone problem) is an information dissemination problem in which each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the other nodes using two-way communications (telephone calls) between the pairs of nodes. During a call between the given two nodes, they exchange the whole information known to them at that moment. In this paper we investigate the $k$-fault-tolerant gossip problem, which is a generalization of the gossip problem, where at most $k$ arbitrary faults of calls are allowed. The problem is to find the minimal number of calls $\tau(n,k)$ needed to guarantee the $k$-fault-tolerance. We construct two classes of $k$-fault-tolerant gossip schemes (sequences of calls) and found two upper bounds of $\tau(n,k)$, which improve the previously known results. The first upper bound for general even $n$ is $\tau(n,k) \leq 1/2 n \lceil\log_2 n\rceil + 1/2 n k$. This result is used to obtain the upper bound for general odd $n$. From the expressions for the second upper bound it follows that $\tau(n,k) \leq 2/3 n k + O(n)$ for large $n$. Assuming that the calls can take place simultaneously, it is also of interest to find $k$-fault-tolerant gossip schemes, which can spread the full information in minimal time. For even $n$ we showed that the minimal time is $T(n,k)=\lceil\log_2 n\rceil + k$., Comment: 19 pages, 5 figures

We use the transfer matrix formalism for dimers proposed by Lieb, and generalize it to address the corresponding problem for arrow configurations (or trees) associated to dimer configurations through Temperley's correspondence. On a cylinder, the arrow configurations can be partitioned into sectors according to the number of non-contractible loops they contain. We show how Lieb's transfer matrix can be adapted in order to disentangle the various sectors and to compute the corresponding partition functions. In order to address the issue of Jordan cells, we introduce a new, extended transfer matrix, which not only keeps track of the positions of the dimers, but also propagates colors along the branches of the associated trees. We argue that this new matrix contains Jordan cells., Comment: 29 pages, 7 figures

We use the transfer matrix formalism for dimers proposed by Lieb, and generalize it to address the corresponding problem for arrow configurations (or trees) associated to dimer configurations through Temperley's correspondence. On a cylinder, the arrow configurations can be partitioned into sectors according to the number of non-contractible loops they contain. We show how Lieb's transfer matrix can be adapted in order to disentangle the various sectors and to compute the corresponding partition functions. In order to address the issue of Jordan cells, we introduce a new, extended transfer matrix, which not only keeps track of the positions of the dimers, but also propagates colors along the branches of the associated trees. We argue that this new matrix contains Jordan cells., Comment: 29 pages, 7 figures

Given a spanning forest on a large square lattice, we consider by combinatorial methods a correlation function of $k$ paths ($k$ is odd) along branches of trees or, equivalently, $k$ loop--erased random walks. Starting and ending points of the paths are grouped in a fashion a $k$--leg watermelon. For large distance $r$ between groups of starting and ending points, the ratio of the number of watermelon configurations to the total number of spanning trees behaves as $r^{-\nu} \log r$ with $\nu = (k^2-1)/2$. Considering the spanning forest stretched along the meridian of this watermelon, we see that the two--dimensional $k$--leg loop--erased watermelon exponent $\nu$ is converting into the scaling exponent for the reunion probability (at a given point) of $k$ (1+1)--dimensional vicious walkers, $\tilde{\nu} = k^2/2$. Also, we express the conjectures about the possible relation to integrable systems., Comment: 27 pages, 6 figures

Given a spanning forest on a large square lattice, we consider by combinatorial methods a correlation function of $k$ paths ($k$ is odd) along branches of trees or, equivalently, $k$ loop--erased random walks. Starting and ending points of the paths are grouped in a fashion a $k$--leg watermelon. For large distance $r$ between groups of starting and ending points, the ratio of the number of watermelon configurations to the total number of spanning trees behaves as $r^{-\nu} \log r$ with $\nu = (k^2-1)/2$. Considering the spanning forest stretched along the meridian of this watermelon, we see that the two--dimensional $k$--leg loop--erased watermelon exponent $\nu$ is converting into the scaling exponent for the reunion probability (at a given point) of $k$ (1+1)--dimensional vicious walkers, $\tilde{\nu} = k^2/2$. Also, we express the conjectures about the possible relation to integrable systems., Comment: 27 pages, 6 figures

Single site height probabilities in the Abelian sandpile model, and the corresponding mean height $$, are directly related to the probability $P_{\rm ret}$ that a loop erased random walk passes through a nearest neighbour of the starting site (return probability). The exact values of these quantities on the square lattice have been conjectured, in particular $ = 25/8$ and $P_{\rm ret} = 5/16$. We provide a rigourous proof of this conjecture by using a {\it local} monomer-dimer formulation of these questions., Comment: 12 pages, 11 figures

Single site height probabilities in the Abelian sandpile model, and the corresponding mean height $$, are directly related to the probability $P_{\rm ret}$ that a loop erased random walk passes through a nearest neighbour of the starting site (return probability). The exact values of these quantities on the square lattice have been conjectured, in particular $ = 25/8$ and $P_{\rm ret} = 5/16$. We provide a rigourous proof of this conjecture by using a {\it local} monomer-dimer formulation of these questions., Comment: 12 pages, 11 figures

We present the detailed calculations of the asymptotics of two-site correlation functions for height variables in the two-dimensional Abelian sandpile model. By using combinatorial methods for the enumeration of spanning trees, we extend the well-known result for the correlation $\sigma_{1,1} \simeq 1/r^4$ of minimal heights $h_1=h_2=1$ to $\sigma_{1,h} = P_{1,h}-P_1P_h$ for height values $h=2,3,4$. These results confirm the dominant logarithmic behaviour $\sigma_{1,h} \simeq (c_h\log r + d_h)/r^4 + {\cal O}(r^{-5})$ for large $r$, predicted by logarithmic conformal field theory based on field identifications obtained previously. We obtain, from our lattice calculations, the explicit values for the coefficients $c_h$ and $d_h$ (the latter are new)., Comment: 28 pages

Following the recent proposal made by Bouttier et al [Phys. Rev. E 76, 041140 (2007)], we study analytically the mobility properties of a single vacancy in the close-packed dimer model on the square lattice. Using the spanning web representation, we find determinantal expressions for various observable quantities. In the limiting case of large lattices, they can be reduced to the calculation of Toeplitz determinants and minors thereof. The probability for the vacancy to be strictly jammed and other diffusion characteristics are computed exactly., Comment: 19 pages, 6 figures

We compute the correlations of two height variables in the two-dimensional Abelian sandpile model. We extend the known result for two minimal heights to the case when one of the heights is bigger than one. We find that the most dominant correlation log r/r^4 exactly fits the prediction obtained within the logarithmic conformal approach., Comment: 5 pages