Annals of Combinatorics 3 (1999) 337-356
Baxter--Guttmann--Jensen Conjecture for Power Series in Directed Percolation Problem
M. Katori1, T. Tsuchiya1, N. Inui2, and H. Kakuno2
1Department of Physics, Faculty of Science and Engineering, Chuo University, Kasuga, Bunkyo-ku, Tokyo 112-8551, Japan
2Department of Mechanical and Intelligent Engineering, Himeji Institute of Technology, 2167 Shosha, Himeji, Hyogo 671-2201, Japan
Received December 11, 1998
AMS Subject Classification: 82C43, 60K35, 30B10, 05A19
Abstract. A probabilistic model of a flow of fluid through a random medium, percolation model, provides a typical example of statistical mechanical problems which are easy to describe but difficult to solve. While the percolation problem on undirected planar lattices is exactly solved as a limit of the Potts models, there still has been no exact solution for the directed lattices. The most reliable method to provide good approximations is a numerical estimation using finite power-series expansion data of the infinite formal power series for percolation probability. In order to calculate higher-order terms in power series, Baxter and Guttmann and Jensen and Guttmann proposed an extrapolation procedure based on an assumption that the correction terms, which show the difference between the exact infinite power series and approximate finite series, are expressed as linear combinations of the Catalan numbers. In this paper, starting from a brief review on the directed percolation problem and the observation by Baxter, Guttmann, and Jensen, we state some theorems in which we explain the reason why the combinatorial numbers appear in the correction terms of power series. In the proof of our theorems, we show several useful combinatorial identities for the ballot numbers, which become the Catalan numbers in a special case. These identities ensure that a summation of products of the ballot numbers with polynomial coefficients can be expanded using the ballot numbers. There is still a gap between our theorems and the Baxter--Guttmann--Jensen observation, and we also give some conjectures. As a generalization of the percolation problem on a directed planar lattice, we present two topics at the end of this paper: The friendly walker problem and the stochastic cellular automata in higher dimensions. We hope that these two topics as well as the directed percolation problem will be of much interest to researchers of combinatorics.
Keywords: directed percolation, formal power series, Catalan numbers and ballot numbers, friendly walker problem, stochastic cellular automata
1. M. Aizenman, The geometry of critical percolation and conformal invariance, In: STATPHYS 19, The 19th IUPAP International Conference on Statistical Physics, World Scientific, Singapore, 1997, pp.104–120.
2. D.K. Arrowsmith and J.W. Essam, Extension of the Kasteleyn--Fortuin formulas to directed percolation, Phys. Rev. Lett. 65 (1990) 3068–3071.
3. D.K. Arrowsmith and J.W. Essam, Chromatic and flow polynomials for directed graphs, J. Combin. Theory Ser. B 62 (1994) 349–362.
4. D.K. Arrowsmith, P. Mason, and J.W. Essam, Vicious walkers, flows and directed percolation, Physica A 177 (1991) 267–272.
5. R.J. Baxter, Exactly Solved Models in Statisitical Mechanics, Academic Press, London, 1982.
6. R.J. Baxter and A.J. Guttmann, Series expansion of the percolation probability for the directed square lattice,J. Phys. A: Math. Gen. 21 (1988) 3193–3204.
7. L.W. Beineke and R.E. Pippert, The number of labeled dissections of k-ball, Math. Ann. 191 (1971) 87–98.
8. J. Blease, Series expansions for the directed-bond percolation problem, J. Phys. C: Solid State Phys. 10 (1977) 917–924.
9. M. Bousquet-Mèlou, Percolation models and animals, Europ. J. Combin. 17 (1996) 343–369.
10. S.R. Broadbent and J.M. Hammersley, Percolation processes I, Crystals and mazes, Cambin. Phil. 53 (1957) 629–641
11. J.L. Cardy, Conformal invariance, In: Phase Transitions and Critical Phenomena, Vol. 11, C. Domb and J.L. Lebowitz, Eds., Academic Press, London, 1987, pp. 55–126.
12. J.L. Cardy, Critical percolation in finite geometries, J. Phys. A: Math. Gen. 25 (1992) L201–L206.
13. J. Cardy and F. Colaiori, Directed percolation and generalized friendly walkers, Phys. Rev. Lett. 82 (1999) 2232–2235.
14. D. Dhar, Diode-resistor percolation in two and three dimensions: I. Upper bounds on critical probability, J. Phys. A: Math. Gen. 15 (1982) 1849–1858.
15. E. Domany and W. Kinzel, Equivalence of cellular automata to Ising models and directed percolation, Phys. Rev. Lett. 53 (1984) 311–314.
16. R. Durrett, Lecture Notes on Particle Systems and Percolation, Wadsworth \& Brooks/Cole, Pacific Grove, California, 1988.
17. J.W. Essam, Percolation and cluster size, In: Phase Transitions and Critical Phenomena, Vol. 2, C. Domb and M.S. Green, Eds., Academic Press, London, 1972, pp. 197–270.
18. J.W. Essam, Percolation theory, Rep. Prog. Phys. 43 (1980) 833--912. See also D.K. Arrowsmith and J.W. Essam, Percolation theory on directed graphs, J. Math. Phys. 18 (1977) 235–238.
19. J.W. Essam and A.J. Guttmann, Vicious walkers and directed polymer networks in general dimensions, Phys. Rev. E 52 (1995) 5849–5862.
20. J.W. Essam, A.J. Guttmann, I. Jensen, and D. TanlaKishani, Directed percolation near a wall, J. Phys. A: Math. Gen. 29 (1996) 1617–1628.
21. C.M. Fortuin and P.W. Kasteleyn, On the random-cluster model I, Introduction and relation to other models, Physica 57 (1972) 536–564.
22. G. Grimmett, Percolation, 2nd Ed., Springer-Verlag, Berlin, 1999.
23. A.J. Guttmann, Indicators of solvability for lattice models, 1998, preprint; Discrete Math., to appear.
24. A.J. Guttmann and I.G. Enting, Solvability of some statistical mechanical systems, Phys. Rev. Lett. 76 (1996) 344–347.
25. A.J. Guttmann, A.L. Owczarek, and X.G. Viennot, Vicious walkers and Young tableaux I: Without walls, J. Phys. A: Math. Gen. 31 (1998) 8123–8135.
26. B.D. Hughes, Random walks and random environments, In: Random Environments, Vol. 2, Clarendon Press, Oxford, 1996.
27. N. Inui, Distribution of poles in a series expansion of the asymmetric directed-bond percolation probability on the square lattice, J. Phys. A: Math. Gen. 31 (1998) 9613–9620.
28. N. Inui and M. Katori, Catalan numbers in a series expansion of the directed percolation probability on a square lattice, J. Phys. A: Math. Gen. 29 (1996) 4347–4364.
29. N. Inui, M. Katori, G. Komatsu, and K. Kameoka, The number of directed compact site animals and extrapolation formula of directed percolation probability, J. Phys. Soc. Jpn. 66 (1997) 1306–1309.
30. C. Itzykson and J.-M. Drouffe, Statistical Field Theory, Vol. 2, Cambridge University Press, Cambridge, 1989, Chpt. 9.
31. I. Jensen, Low-density series expansions for directed percolation on square and triangular lattice, J. Phys. A: Math. Gen. 29 (1996) 7013–7040.
32. I. Jensen, Temporally disordered bond percolation on the directed square lattice, Phys. Rev. Lett. 77 (1996) 4988–4991.
33. I. Jensen and A.J. Guttmann, Series expansions of the percolation probability for directed square and honeycomb lattices, J. Phys. A: Math. Gen. 28 (1995) 4813–4833.
34. I. Jensen and A.J. Guttmann, Series expansions of the percolation probability on the directed triangular lattice, J. Phys. A: Math. Gen. 29 (1996) 497–517.
35. I. Jensen and A.J. Guttmann, Extrapolation procedure for low-temperature series for the square lattice spin-1 Ising model, J. Phys. A: Math. Gen. 29 (1996) 3817–3836.
36. P.W. Kasteleyn and C.M. Fortuin, Phase transitions in lattice systems with random local properties, J. Phys. Soc. Jpn. Suppl. 26 (1969) 11–14.
37. M. Katori and N. Inui, Ballot number representation of the percolation probability series for the directed square lattice, J. Phys. A: Math. Gen. 30 (1997) 2975–2994.
38. M. Katori, N. Inui, G. Komatsu, and K. Kameoka, Hypergeometric series in a series expansion of the directed-bond percolation probability on the square lattice, J. Stat. Phys. 86 (1997) 37–55.
39. M. Katori and H. Tsukahara, Two-neighbour stochastic cellular automata and their planar lattice duals, J. Phys. A: Math. Gen. 28 (1995) 3935–3957.
40. H. Kesten, Percolation Theory for Mathematicians, Birkhäuser, Boston, 1982.
41. W. Kinzel, Phase transitions of cellular automata, Z. Phys. B 58 (1985) 229–244.
42. T.M. Liggett, Survival of discrete time growth models, with applications to oriented percolation, Ann. Appl. Prob. 5 (1994) 613–636.
43. P. Martin, Potts Models and Related Problems in Statistical Mechanics, World Scientific, Singapore, 1991.
44. R.N. Onody and U.P.C. Neves, Series expansion of the directed percolation probability, J. Phys. A: Math. Gen. 25 (1992) 6609–-6615.
45. J. Riordan, Combinatorial Identities, Robert E. Krieger, Huntington, New York, 1979.
46. N.J.A. Sloane, A Handbook of Integer Sequences, Academic Press, New York, 1973.
47. H. Spohn, Large Scale Dynamics of Interacting Particles, Springer-Verlag, Berlin, 1991.
48. R.P. Stanley, Differential finite power series, Europ. J. Combin. 1 (1980) 175–188.
49. D. Stauffer and A. Aharony, Introduction to Percolation Theory, 2nd Ed., Taylor Francis, London, 1992.
50. T. Tsuchiya and M. Katori, Chiral Potts models, friendly walkers and directed percolation problem, J. Phys. Soc. Jpn. 67 (1998) 1655–1666.
51. F.Y. Wu, The Potts model, Rev. Mod. Phys. 54 (1982) 235–268.