Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-24T01:41:40.551Z Has data issue: false hasContentIssue false
  • English
  • Français

Integer Partitions, Tilings of 2D-gons and Lattices

Published online by Cambridge University Press:  15 February 2003

Matthieu Latapy
Matthieu Latapy*
Affiliation:
LIAFA, Université Paris 7, 2 place Jussieu, 75005 Paris, France; [email protected].
Get access

Abstract

In this paper, we study two kinds of combinatorial objects, generalized integer partitions and tilings of 2D-gons (hexagons, octagons, decagons, etc.). We show that the sets of partitions, ordered with a simple dynamics, have the distributive lattice structure. Likewise, we show that the set of tilings of a 2D-gon is the disjoint union of distributive lattices which we describe. We also discuss the special case of linear integer partitions, for which other dynamical models exist.

Keywords

Integer partitionstilings of 2D-gonslatticesSand Pile Model discrete dynamical models.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 36 , Issue 4 , October 2002 , pp. 389 - 399
Copyright
© EDP Sciences, 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

G.E. Andrews, The Theory of Partitions. Addison-Wesley Publishing Company, Encyclopedia Math. Appl. 2 (1976).
Bailey, G.D., Coherence and enumeration of tilings of 3-zonotopes. Discrete Comput. Geom. 22 (1999) 119-147. CrossRef
G.D. Bailey, Tilings of zonotopes: Discriminantal arrangements, oriented matroids, and enumeration, Ph.D. Thesis. University of Minnesota (1997).
Brylawski, T., The lattice of integer partitions. Discrete Math. 6 (1973) 210-219.
B.A. Davey and H.A. Priestley, Introduction to Lattices and Orders. Cambridge University Press (1990).
N.G. de Bruijn, Algebraic theory of penrose's non-periodic tilings of the plane. Konink. Nederl. Akad. Wetensch. Proc. Ser. A 43 (1981).
N.G. de Bruijn, Dualization of multigrids. J. Phys. France Coloq (1981) 3-9.
Destainville, N., Mosseri, R. and Bailly, F., Configurational entropy of codimension-one tilings and directed membranes. J. Statist. Phys. 87 (1997) 697. CrossRef
N. Destainville, R. Mosseri and F. Bailly, Fixed-boundary octogonal random tilings: A combinatorial approach. Preprint (1999).
N. Destainville, Entropie configurationnelle des pavages aléatoires et des membranes dirigées, Ph.D. Thesis. University Paris VI (1997).
Elnitsky, S., Rhombic tilings of polygons and classes of reduced words in coxeter groups. J. Combin. Theory 77 (1997) 193-221. CrossRef
Goles, E. and Kiwi, M.A., Games on line graphs and sand piles. Theoret. Comput. Sci. 115 (1993) 321-349. CrossRef
Kenyon, R., Tilings of polygons with parallelograms. Algorithmica 9 (1993) 382-397. CrossRef
M. Latapy and H.D. Phan, The lattice of integer partitions and its infinite extension, in DMTCS, Special Issue, Proc. of ORDAL'99. Preprint (to appear) available at http://www.liafa.jussieu.fr/ latapy/
M. Latapy, Generalized integer partitions, tilings of zonotopes and lattices, in Proc. of the 12-th international conference Formal Power Series and Algebraic Combinatorics (FPSAC'00) , edited by A.A. Mikhalev, D. Krob and E.V. Mikhalev. Springer (2000) 256-267. Preprint available at http://www.liafa.jussieu.fr/ latapy/
Latapy, M., Mantaci, R., Morvan, M. and Duong Phan, Ha, Structure of some sand piles model. Theoret. Comput. Sci. 262 (2001) 525-556. Preprint available at http://www.liafa.jussieu.fr/ latapy/ CrossRef
R.P. Stanley, Ordered structures and partitions. Mem. ACM 119 (1972).
G. Ziegler, Lectures on Polytopes. Springer-Verlag, Grad. Texts in Math. (1995).