<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 3" %>
Lattice Structure and Convergence of a Game of Cards
Eric Goles1, Michel Morvan2, and Ha Duong Phan3
1Departamento de Ingenier赤a Matem芍tica, Escuela de Ingenier赤a, Universidad de Chile, Casilla 170-Correo 3, Santiago, Chile
egoles@dim.uchile.cl
2LIAFA, Universit谷 Denis Diderot Paris 7 and Institut Universitaire de France, Case 7014-2Place Jussieu-75256 Paris Cedex, France
morvan@liafa.jussieu.fr
3LIAFA, Universit谷 Denis Diderot Paris 7, Case 7014-2, Place Jussieu-75256 Paris Cedex, France
phan@liafa.jussieu.fr
Annals of Combinatorics 6 (3) p.327-335 September, 2002
AMS Subject Classification: 91A46
Abstract:
We study the dynamics of the so-called Game of Cards by using tools developed in the context of discrete dynamical systems. We extend a result of [4] and [10] (the last one in the context of distributed systems) that established a necessary and sufficient condition for the game to converge. We precisely describe the lattice structure of the set of configurations and we state bounds for the convergence time.
Keywords: integer composition, order, lattice, convergence

References:

1. G. Birkhoff, Lattice Theory, American Mathematical Society, 1967.

2. T. Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973) 201每219.

3. B.A. Davey and H.A. Priestley, Introduction to Lattices and Order, Cambridge Mathematical Textbooks, Cambridge University Press, Cambridge, 1990.

4. J. Desel, E. Kindler, T. Vesper, and R. Walter, A simplified proof for the self-stabilizing protocol: a game of cards, Inform. Proc. Lett. 54 (1995) 327每328.

5. K. Eriksson, Strongly convergent games and Coxeter groups, Ph.D. Thesis, Department of Mathematics, KTH, S-100 44 Stockholm, Sweden, 1993.

6. E. Goles and M.A. Kiwi, Games on line graphs and sand piles, Theoret. Comput. Sci. 115 (1993) 321每349.

7. E. Goles, M. Morvan, and H.D. Phan, About the dynamics of some systems based on integer partitions and compositions, FPSAC*2000, pp. 214每225.

8. E. Goles, M. Morvan, and H.D. Phan, Sandpiles and order structure of integer partitions, Discrete Appl. Math. 117 (2002) 51每64.

9. C. Greene and D.J. Kleitman, Longest chains in the lattice of integer partitions ordered by majorization, Europ. J. Combin. 7 (1986) 1每10.

10. S.-T. Huang, Leader election in uniform rings, ACM Trans. Program. Lang. Systems 15 (3) (1993) 563每573.

11. M. Latapy and H.D. Phan, The lattice structure of chip firing games and related models, Phys. D 155 (2001) 69每82.