T-tetrominoes tiling's Markov chain mixes fast
Review articleOpen access
Abstract:

AbstractKorn and Pak (2007) [3] conjectured that there exists a fully polynomial randomized approximation scheme (fpras) for approximating the number of ways of tiling a 4nĂ—4m rectangular lattice with T-tetrominoes. Using a flow argument, we prove this conjecture in affirmative by showing that the mixing time of an appropriate Markov chain is polynomial in the area of the lattice.

Request full text

References (0)

Cited By (0)

No reference data.
No citation data.
Advertisement
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!