← All problems

Conjecture on the complexity of tromino tilings of extended domino-deficient rectangles

19 years old · documented by

Let NT(m,n)N_T(m,n) denote the number of tromino tilings of an m×nm\times n rectangle. Consider an extended domino-deficient rectangle with minimal dimensions m×n′m\times n', where n′>nn'>n. Complexity conjecture. The complexity of the number of tromino tilings changes from NT(m,n)N_T(m,n) to

O((m+n)⋅NT(m,n)).\mathcal{O}((m+n)\cdot N_T(m,n)).

This conjecture proposes that introducing a minimal extension and a domino deficiency increases the tiling-count complexity by a factor linear in the sum of the rectangle dimensions. The preceding 4×n4\times n analysis motivates the claim, but no general proof or resolution is given here.

References
  1. Mridul Aanjaneya, “Tromino tilings of Domino-Deficient Rectangles”, arXiv:cs/0606059 (2007).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.