Generating random elements of finite distributive lattices

MaRDI QIDQ1378529zbMATH OpenFDO

Authors James Propp

Publication date 15 February 1998

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9801066, https://eudml.org/doc/119239, http://www.emis.de/journals/EJC/Volume_4/Abstracts/v4i2r15ab.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Designs and configurations (05B99)

Abstract: This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas of the author and David Wilson for using ``coupling from the past to remove initialization bias from Monte Carlo randomization. The article describes several applications to specific kinds of combinatorial objects such as tilings, constrained lattice paths, and alternating-sign matrices.

Review text

Summary: This survey article describes a recent advance in the area of random generation, with applications to plane partitions, domino tilings, alternating sign matrices, and many other sorts of combinatorial objects. The algorithm is of the ``random walk or ``Monte Carlo variety, but unlike many such algorithms it does not have any initialization bias. The heart of the algorithm is the method of coupling from the past explored by David Wilson and myself in a joint article. For the sake of readability and motivation, I will start by focusing on the application of our method to plane partitions.

Recommendations

• On the probability of generating a lattice
• Distributively generated lattices
• Generating random elements of a finite group
• scientific article; zbMATH DE number 3978386
• Random generation of combinatorial structures from a uniform distribution
• scientific article; zbMATH DE number 4031760
• scientific article; zbMATH DE number 6168348
• Generating random elements in finite groups.
• On finite pseudorandom binary lattices
• A vectorizable random lattice

Cited in

(14)

• Shuffling algorithm for boxed plane partitions
• Another involution principle-free bijective proof of Stanley's hook-content formula
• Random generation of direct sums of finite non-degenerate subspaces
• A refinement of weak order intervals into distributive lattices
• Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings
• Mixing times of Markov chains of 2-orientations
• Center stable matchings and centers of cover graphs of distributive lattices
• Orientation-Constrained Rectangular Layouts
• Rotor walks on transient graphs and the wired spanning forest
• Perfect sampling algorithms for Schur processes
• Generalized loop-erased random walks and approximate reachability
• Tilings of rectangles with T-tetrominoes
• \(q\)-distributions on boxed plane partitions
• A characterization of flip-accessibility for rhombus tilings of the whole plane

This page was built for publication: Generating random elements of finite distributive lattices

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