Source-linked AI summary
Improved bounds for the variant of lazy cops and robbers on generalized hypercubes
Anand Babu, Ashwin Jacob, Karunakaran Murali Krishnan, Reshma Roy, Sreekala S
TL;DR
Lazy Cops and Robbers asks how few cops can force capture on generalized hypercubes, with prior bounds carrying a logarithmic factor. This paper uses linear algebraic techniques and a construction whose size is asymptotically optimal up to a constant factor.
Problem
The paper studies the minimum number of cops needed to force capture in Lazy Cops and Robbers on generalized hypercubes, where prior generalized-hypercube bounds involved a logarithmic factor.
Method
The paper uses linear algebraic techniques and constructs a set whose size is analyzed across the relevant parameter ranges.
Results
O(m^k/k^d) is the size of the construction in Lemma 2.2, and this size is asymptotically optimal up to a constant factor.
Takeaways & Limitations
The resulting bounds remove the logarithmic factor arising from standard domination-number estimates on graphs induced by levels.
Abstract
from arXiv · showhide
In the speed-$d$ variant of Lazy Cops and Robbers, the cops and the robber alternate turns. On a cop turn, either all cops remain stationary or one cop traverses a path of length at most $d$. On a robber turn, the robber either remains stationary or moves to an adjacent vertex. Let $c_{\mathrm L}^{(d)}(G)$ denote the minimum number of cops that can force a cop to occupy the robber's vertex after finitely many turns. We study this variant on the generalized hypercube $Q(n,m)$, whose vertex set is ${\{0,1,\ldots,m\}}^n$. For fixed integers $m\geq2$ and $d\geq1$, we prove that, as $n\to\infty$, \[ c_{\mathrm L}^{(d)}(Q(n,m)) =O\!\left(\frac{{(m+1)}^n}{n^{d+1/2}}\right). \] When $d=1$, our result improves the upper bound of Sim, Tan, and Wong for the ordinary lazy cop number by a factor of $\log n$.
1 Introduction
The paper studies speed-d Lazy Cops and Robbers on generalized hypercubes and develops linear-algebraic techniques to improve earlier bounds. The speed-d game permits the moving cop to traverse a path of length at most d.
- Speed-d Lazy Cops and Robbers allows one cop to traverse a path of length at most d on each cop turn, while the robber moves at most one edge.
- Q(n,m) has vertex set {0,1,…,m}^n, with adjacency defined by differing in exactly one coordinate.
- Earlier work extended the level-sweeping strategy from hypercubes to generalized hypercubes.
- The earlier bound incurred a logarithmic factor from applying a standard domination-number bound to graphs induced by the levels.
- The paper uses linear algebraic techniques to obtain improved bounds for fixed m and d as n tends to infinity.
2 Main Result
The main argument constructs distance-d dominating sets for each level of the generalized hypercube and uses them in a level-sweeping capture strategy. The construction is asymptotically optimal within each support class up to a constant factor and yields the theorem.
- Level-sweeping strategy: Distance-d dominating sets on every level support a level-sweeping strategy for the speed-d game.The strategy transfers two cop teams successively between occupied sets while preventing the robber from crossing the swept level without entering it.
- Construction: Each support class of a level induces a Cartesian product K_m□k, and the construction applies independently to every support class.The resulting union B_k distance-d dominates the entire level L_k.
- Construction: The construction uses additive cyclic-group labels and a homomorphism whose kernel supplies the distance-d dominating set.The labels are arranged across d direct-sum components, with at most d coordinates altered to reach the kernel.
- Construction: O(m^k/k^d) is asymptotically optimal up to a constant factor for distance-d dominating sets in K_m□k.
- Main bound: The binomial estimates control both central and lower-tail ranges of k in establishing the required bound.The central range uses fixed-parameter binomial point-mass estimates, while the lower tail is controlled by a Chernoff inequality.
Declaration on the Origin of the Proof and Use of Generative AI
The authors state that the d = 1 construction was developed through AI-assisted mathematical exploration, followed by independent reconstruction, review, and verification by the named authors.
- The d = 1 construction originated through AI-assisted mathematical exploration with OpenAI Codex.
- The named authors independently reconstructed, reviewed, and verified every mathematical argument and take responsibility for the claims, citations, and remaining errors.