Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.17698 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913993532112896 |
|---|---|
| author | Liang, Kai |
| author_facet | Liang, Kai |
| contents | This paper presents an algorithm for computing the contraction of two-dimensional tensor networks on a square lattice; and we combine it with solving congruence equations to compute the exact enumeration (including weighted enumeration) of Wang tilings. Based on this, the paper demonstrates how to transform other tiling enumeration problems (such as those of polyominoes) into Wang tiling enumeration problems, thereby solving them using this algorithm.
Our algorithm extends the sequence length records for dozens of sequences defined by polyomino tiling enumeration on chessboards on the OEIS website, covering numerous of different polyomino sets, including I-polyominoes, tetrominoes, pentominoes, etc. This demonstrates the high efficiency and strong universality of the algorithm for solving exact tiling enumeration problems.
In addition, the theory and techniques used in the algorithm establish a bridge between tensor network contractions and tiling enumeration, where the former provides a theoretical foundation for solving problems in the latter, while the latter offers an intuitive combinatorial interpretation of the former. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17698 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving tiling enumeration problems by tensor network contractions Liang, Kai Combinatorics 05A15 (Primary), 68R05 This paper presents an algorithm for computing the contraction of two-dimensional tensor networks on a square lattice; and we combine it with solving congruence equations to compute the exact enumeration (including weighted enumeration) of Wang tilings. Based on this, the paper demonstrates how to transform other tiling enumeration problems (such as those of polyominoes) into Wang tiling enumeration problems, thereby solving them using this algorithm. Our algorithm extends the sequence length records for dozens of sequences defined by polyomino tiling enumeration on chessboards on the OEIS website, covering numerous of different polyomino sets, including I-polyominoes, tetrominoes, pentominoes, etc. This demonstrates the high efficiency and strong universality of the algorithm for solving exact tiling enumeration problems. In addition, the theory and techniques used in the algorithm establish a bridge between tensor network contractions and tiling enumeration, where the former provides a theoretical foundation for solving problems in the latter, while the latter offers an intuitive combinatorial interpretation of the former. |
| title | Solving tiling enumeration problems by tensor network contractions |
| topic | Combinatorics 05A15 (Primary), 68R05 |
| url | https://arxiv.org/abs/2503.17698 |