The lattice of integer partitions and its infinite extension

DOI10.1016/J.DISC.2008.02.002MaRDI QIDQ1024442zbMATH OpenOpenAlexFDO

Authors Matthieu Latapy, Thi Ha Duong Phan

Publication date 17 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0008020

zbMATH Keywords

latticeinteger partitionssand pile modelYoung latticedominance orderingdiscrete dynamical models

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17)

Abstract: In this paper, we use a simple discrete dynamical model to study integer partitions and their lattice. The set of reachable configurations of the model, with the order induced by the transition rule defined on it, is the lattice of all partitions of an integer, equipped with a dominance ordering. We first explain how this lattice can be constructed by an algorithm in linear time with respect to its size by showing that it has a self-similar structure. Then, we define a natural extension of the model to infinity, which we compare with the Young lattice. Using a self-similar tree, we obtain an encoding of the obtained lattice which makes it possible to enumerate easily and efficiently all the partitions of a given integer. This approach also gives a recursive formula for the number of partitions of an integer, and some informations on special sets of partitions, such as length bounded partitions.

Recommendations

• Partitions of an Integer into Powers
• Strict partitions and discrete dynamical systems
• On the partition lattice of all integers
• The lattice of partitions of a positive integer
• Integer partitions in discrete dynamical models and ECO method

Cites work

• scientific article; zbMATH DE number 3577263 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 194916 (Why is no real title available?)
• Counting paths in Young's lattice
• Disks, Balls, and Walls: Analysis of a Combinatorial Game
• Games on line graphs and sand piles
• Integer Partitions, Tilings of2D-gons and Lattices
• Lattice structure and convergence of a game of cards
• Partitions of an Integer into Powers
• Sandpiles and order structure of integer partitions
• Structure of some sand piles model
• The lattice of integer partitions
• The lattice structure of chip firing games and related models

Cited in

(26)

• scientific article; zbMATH DE number 1504589 (Why is no real title available?)
• Chop vectors and the lattice of integer partitions
• On sequences of elementary transformations in the integer partitions lattice
• The lattice of partitions of a positive integer
• Partitions of an Integer into Powers
• Parallel rank of two sandpile models of signed integer partitions
• Sandpile models and lattices: a comprehensive survey
• Recursion over partitions
• Arrow relations in lattices of integer partitions
• On the partition lattice of all integers
• Lattices of lattice paths
• Dominance order on signed integer partitions
• On the trajectories of a particle in a translation invariant involutive field
• A survey on the stability of (extended) linear Sand Pile model
• Sand piles models of signed partitions with d piles
• scientific article; zbMATH DE number 2061623 (Why is no real title available?)
• Strict partitions and discrete dynamical systems
• Introduction to the integer partition lattice
• The Lattice Structure of Equally Extended Signed Partitions
• Extensions of infinite partition regular systems
• scientific article; zbMATH DE number 4218566 (Why is no real title available?)
• On the set of integer partition and closed form for its length in special cases
• Integer Partitions, Tilings of2D-gons and Lattices
• Representing partition lattices through FCA
• On integer partitions and continued fraction type algorithms
• Two sided Sand Piles Model and unimodal sequences

This page was built for publication: The lattice of integer partitions and its infinite extension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024442)