Asymptotic Bounds for Irredundant Covers of Square Grids by 2 x 2 Cards
Abstract
We study an irredundant covering of an m × m square grid by 2 × 2 cards, where cards may overlap and every card must lie entirely inside the grid. Every square of the grid must be covered, and every card must contain at least one square that is covered only by itself. Let F(m) denote the maximum number of cards in such an irredundant cover. We develop a general framework for bounding the maximum possible size of such an irredundant cover based on square multiplicities, double counting, and local geometric restrictions arising around highly covered squares. These arguments yield a general upper bound whose leading term is 1/2m2, accompanied by a negative linear term. In the opposite direction, we construct a family of irredundant covers based on a density-1/2 covering pattern, referred to as the period-four staircase pattern, together with a boundary-repair construction. Thus, we obtain a lower bound with the same leading term and a linear-order error, proving that for every m≥6, 2m/9 ≤ 1/2m2−F(m) ≤ 2m−3, and consequently that the maximum density of an irredundant cover tends to 1/2 as m→∞. The known 10× 10 case is used as motivation and as a finite benchmark for the general theory.
Related
BibTeX
@misc{eruysal2026asymptotic,
title = {{Asymptotic Bounds for Irredundant Covers of Square Grids by 2 x 2 Cards}},
author = {Aksel Eruysal and S. Kaan Gürbüzer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10063},
eprint = {2609.10063},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10063},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Asymptotic Bounds for Irredundant Covers of Square Grids by 2 x 2 Cards
AU - Aksel Eruysal
AU - S. Kaan Gürbüzer
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.10063
UR - https://arxiv.org/abs/2609.10063
AB - We study an irredundant covering of an m × m square grid by 2 × 2 cards, where cards may overlap and every card must lie entirely inside the grid. Every square of the grid must be covered, and every card must contain at least one square that is covered only by itself. Let F(m) denote the maximum number of cards in such an irredundant cover. We develop a general framework for bounding the maximum possible size of such an irredundant cover based on square multiplicities, double counting, and local geometric restrictions arising around highly covered squares. These arguments yield a general upper bound whose leading term is 1/2m^2, accompanied by a negative linear term. In the opposite direction, we construct a family of irredundant covers based on a density-1/2 covering pattern, referred to as the period-four staircase pattern, together with a boundary-repair construction. Thus, we obtain a lower bound with the same leading term and a linear-order error, proving that for every m≥6, 2m/9 ≤ 1/2m^2−F(m) ≤ 2m−3, and consequently that the maximum density of an irredundant cover tends to 1/2 as m→∞. The known 10× 10 case is used as motivation and as a finite benchmark for the general theory.
ER -