New enumerative results on two-dimensional directed animals
type: Item
instance of: scholarly article
title: New enumerative results on two-dimensional directed animals
zbMATH Open document ID: 0974.05002
DOI: 10.1016/S0012-365X(97)00109-X
author: Mireille Bousquet-Mélou
published in: Discrete Mathematics
publication date: 1998-07-23T00:00:00Z
review text: An animal \(A\) on a graph \(G\) is a finite set of vertices of \(G\) which are connected in the sense that any two vertices of \(A\) are connected by a path in \(G\) having all its vertices in \(A\). These objects are of interest in statistical mechanics as well as combinatorics, since directed animals are related to directed (site) percolation models. Indeed, as shown by \textit{D. Dhar} [Equivalence of the two-dimensional directed site animal problem to Baxter's hard square lattice gas model, Phys. Rev. Lett. 49, 959-962 (1983); Exact solution of a directed-site animals-enumeration problem in three dimensions, Phys. Rev. Lett. 51, No. 10, 853-856 (1983)], enumerating directed animals on a certain graph corresponds to solving a hard particle model on a different graph. After a thorough review of results, methods and open problems in this field, the author extends Dhar's idea to show that many of the open questions reduce to finding the position generating function and the (bivariate) perimeter and area generating function for directed animals on square lattices. Moreover, each of these generating functions is essentially the density of a one-dimensional gas model given by the stationary distribution of a probabilistic transition. Although not solved in general, certain special cases give new bivariate generating functions for both square and triangular lattices from which several other generating function results follow as corollaries.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 82B41
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 1135933
zbMATH Keywords: animals
zbMATH Keywords: generating functions
zbMATH Keywords: gas models
Wikidata QID: Q56112478
reviewed by: Jennifer R.Galovich
MaRDI profile type: Publication
cites work: Q3324796
cites work: Animaux et arbres guingois. (Animals and guingois trees)
cites work: Percolation models and animals
cites work: Some exact results for moments of 2D directed animals
cites work: Equivalence of the two-dimensional directed animal problem to a one- dimensional path problem
cites work: On the number of lattice animals embeddable in the square lattice
cites work: Solvability of Some Statistical Mechanical Systems
cites work: A Procedure for Improving the Upper Bound for the Number of n-Ominoes
cites work: Non-negative matrices and Markov chains. 2nd ed
cites work: Q3754627
description: scientific article; zbMATH DE number 1135933