Greedy lattice animals. I: Upper bounds (Q1313075)

Let \(\{X_ v, v \in Z^ d\}\) be an i.i.d. family of positive random variables. For each set \(\xi\) of vertices of \(Z^ d\), its weight is defined as \(S(\xi) = \sum_{v \in \xi} X_ v\). A greedy lattice animal of size \(n\) is a connected subset of \(Z^ d\) of \(n\) vertices containing the origin, and whose weight is maximal among all such sets. Denote by \(N_ n\) this maximal weight. The authors prove that, if the expectation of \(X^ d_ v (\log^ + X_ v)^{d + \alpha}\) is finite for some \(\alpha > 0\), then with probability 1, \(N_ n \leq Mn\) eventually for some finite constant \(M\). They also derive estimates for the tail of the distribution of \(N_ n\). It is shown that this model fits a number of optimization problems among which we cite PERT networks, \(\rho\)- percolation [\textit{M. V. Menshikov} and \textit{S. A. Zuev}, in: Probabilistic methods in discrete mathematics, Prog. Pure \& Appl. Discret. Math. 1, 337-347 (1993)] and random colorings [\textit{L. Fontes} and \textit{Ch. M. Newman}, Ann. Appl. Probab. 3, No. 3, 746-762 (1993; Zbl 0780.60101)].