PreprintarXiv licencearXiv
Intractable enumeration problems are like Russian nesting dolls: structural properties of monomer-dimer coverings on two-dimensional quadratic lattices
Abstract
Counting the number of coverings of s dimers on two-dimensional quadratic lattices is considered as intractable and belongs to \#P-complete class. We reveal the structure of the exact solution to the problem and provide an explicit formula for it, which includes s−1 nesting sums. This results in an exponential time complexity of O(2s). The solution is explicitly determined by a sequence that exhibits double-exponential growth.
Related
- π-Properties, Uniformly Convexity and Uniform Ball Coverings Properties
- Fractal Hyper-Trees: Combinatorial Enumeration, Symmetry Properties, and Ultrametric Structures
- The higher-dimensional Shepp problem: an exact criterion for random ball coverings of tori
- Commutativity Criteria and Structural Properties of Prime Near-Rings Admitting Right Generalized Derivations on Specific Ideals
- Structural and Dynamical Properties of Subfactor Commuting Squares
BibTeX
@misc{kong2026intractable,
title = {{Intractable enumeration problems are like Russian nesting dolls: structural properties of monomer-dimer coverings on two-dimensional quadratic lattices}},
author = {Yong Kong},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19231},
eprint = {2609.19231},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19231},
}
RIS
TY - UNPB
TI - Intractable enumeration problems are like Russian nesting dolls: structural properties of monomer-dimer coverings on two-dimensional quadratic lattices
AU - Yong Kong
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.19231
UR - https://arxiv.org/abs/2609.19231
AB - Counting the number of coverings of s dimers on two-dimensional quadratic lattices is considered as intractable and belongs to \#P-complete class. We reveal the structure of the exact solution to the problem and provide an explicit formula for it, which includes s−1 nesting sums. This results in an exponential time complexity of O(2^s). The solution is explicitly determined by a sequence that exhibits double-exponential growth.
ER -