PreprintarXiv licencearXiv
Improved bounds for the lazy cops and robbers on generalized hypercubes
Abstract
In Lazy Cops and Robbers, at most one cop moves on each cop turn. We study the lazy cop number of the generalized hypercube Q(n,m), whose vertex set is {0,1,…,m}n. For each fixed integer m≥2, we prove the asymptotic upper bound cL(Q(n,m))=O (((m+1)n)/n3/2). This result improves the upper bound of Sim, Tan, and Wong by a factor of log n. The proof combines a moving dominating-set argument with an explicit dominating-set construction inside the support classes of each level. As a separate domination result, we show that, for fixed integers m≥2 and d≥1, the Hamming graph Km□ k has a distance-d dominating set of asymptotic size O(mk/kd). This order is optimal up to a constant factor.
Related
- Constructing longer snakes and improved asymptotic bounds in hypercubes
- Sharp lower bounds for sumsets in hypercubes
- Improved bounds for the two-point logarithmic Chowla conjecture
- Improved bounds in Birch's theorem for forms in many variables
- Improved Bounds For The Lipschitz Retraction Constant In Classical Banach Spaces
BibTeX
@misc{babu2026improved,
title = {{Improved bounds for the lazy cops and robbers on generalized hypercubes}},
author = {Anand Babu and Ashwin Jacob and Karunakaran Murali Krishnan and Reshma Roy and Sreekala S},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00720},
eprint = {2609.00720},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00720},
}
RIS
TY - UNPB
TI - Improved bounds for the lazy cops and robbers on generalized hypercubes
AU - Anand Babu
AU - Ashwin Jacob
AU - Karunakaran Murali Krishnan
AU - Reshma Roy
AU - Sreekala S
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.00720
UR - https://arxiv.org/abs/2609.00720
AB - In Lazy Cops and Robbers, at most one cop moves on each cop turn. We study the lazy cop number of the generalized hypercube Q(n,m), whose vertex set is {0,1,…,m}^n. For each fixed integer m≥2, we prove the asymptotic upper bound c_L(Q(n,m))=O (((m+1)^n)/n^3/2). This result improves the upper bound of Sim, Tan, and Wong by a factor of log n. The proof combines a moving dominating-set argument with an explicit dominating-set construction inside the support classes of each level. As a separate domination result, we show that, for fixed integers m≥2 and d≥1, the Hamming graph K_m^□ k has a distance-d dominating set of asymptotic size O(m^k/k^d). This order is optimal up to a constant factor.
ER -