The lattice of integer partitions and its infinite extension

DOI10.1016/J.DISC.2008.02.002zbMATH Open1168.05007arXivmath/0008020OpenAlexW1973900801MaRDI QIDQ1024442FDOQ1024442

Thi Ha Duong Phan, Matthieu Latapy

Publication date: 17 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

latticeinteger partitionssand pile modelYoung latticedominance orderingdiscrete dynamical models

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The lattice of integer partitions
• Disks, Balls, and Walls: Analysis of a Combinatorial Game
• Games on line graphs and sand piles
• Sandpiles and order structure of integer partitions
• Structure of some sand piles model
• Integer Partitions, Tilings of2D-gons and Lattices
• Counting paths in Young's lattice
• The lattice structure of chip firing games and related models
• Lattice structure and convergence of a game of cards
• Partitions of an Integer into Powers

Cited In (20)

• Title not available (Why is that?)
• Chop vectors and the lattice of integer partitions
• Partitions of an Integer into Powers
• The lattice of partitions of a positive integer
• Parallel rank of two sandpile models of signed integer partitions
• Arrow relations in lattices of integer partitions
• Sandpile models and lattices: a comprehensive survey
• Lattices of lattice paths
• Dominance order on signed integer partitions
• A survey on the stability of (extended) linear Sand Pile model
• Sand piles models of signed partitions with \(d\) piles
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Integer Partitions, Tilings of2D-gons and Lattices
• Representing partition lattices through FCA
• 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)