CS Paper Radar

Improved bounds for the lazy cops and robbers on generalized hypercubes

Anand Babu, Ashwin Jacob, Karunakaran Murali Krishnan, Reshma Roy, Sreekala S

cs.DM math.CO ·submitted 2026-09-01 04:50 UTC · v2
theory

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,\ldots,m\}}^n$. For each fixed integer $m\geq2$, we prove the asymptotic upper bound $$c_{\mathrm{L}}(Q(n,m))=O\!\left(\frac{{(m+1)}^n}{n^{3/2}}\right).$$ 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\geq2$ and $d\geq1$, the Hamming graph $K_m^{\square k}$ has a distance-$d$ dominating set of asymptotic size $O(m^k/k^d)$. This order is optimal up to a constant factor.

Comment
5 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Near-Optimal Distributed Domination in Planar Graphs

cs.DS cs.DC ·2026-09-26 ·Wojciech Wawrzyniak
theoryhighly cited similarity 0.65
Abstract · 19 pages, 7 figures

We give a deterministic $(8+\varepsilon)$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\varepsilon>0$. This improves the previous ratio $11+\varepsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is only one above the known lower bound of $7$. Our result closes three quarters of the previous gap, reducing it from $4$ to $1$. Our main contribution is a sharp structural bound. For any dominating set $D$, assigning each vertex outside $D$ to a neighboring center gives disjoint owner blocks. If $k_x$ counts the other blocks containing a neighbor of $x$, then $\sum_{x\notin D}(k_x-2)^+\le(4|D|-12)^+$, where $z^+=\max\{z,0\}$. The bound holds for every such assignment, and equality holds for arbitrarily large minimum dominating sets. We use this bound in their three-phase framework, with new parameters and the same final linear-programming procedure. The algorithm requires neither a planar embedding nor the graph size, and its round bound depends only on $\varepsilon$. The transfer theorem of Bonamy et al. also gives a deterministic $(25+\varepsilon)$-approximation on graphs of bounded Euler genus, with a round bound depending only on $\varepsilon$ and the genus.

0.36

Almost tight distributed approximation for domination in sparse graph classes

cs.DC cs.DMcs.DS ·2026-10-22 ·Timothé Picavet
similarity 0.64
Abstract · 27 pages, 4 figures

We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion. In more detail, for fixed $d$ and $\varepsilon>0$, we give a new deterministic constant-round LOCAL algorithm for Minimum Dominating Set on graphs of maximum average degree at most $d$ and bounded depth-one shallow-minor density. Its approximation ratio is $d+1+\varepsilon$, which is optimal up to $\varepsilon$ for every even integer $d\geq 2$. This improves on the recent results of Amiri and Siebertz by extending beyond proper minor-closed classes. From this algorithm, we derive almost-tight constant-round approximations for a number of graph classes. We get $(7+\varepsilon)$-approximations for planar graphs and graphs of bounded Euler genus, and $(5+\varepsilon)$-approximations for their triangle-free subclasses. This answers the $7+\varepsilon$ question of Wawrzyniak positively, and matches the recent results of Amiri and Siebertz. We also apply our algorithm to classes of bounded queue-number or stack-number, obtaining bounds that are tight up to $\varepsilon$. Additionally, we answer questions of Amiri and Siebertz about improving the dependence of the round complexity on $1/\varepsilon$ and obtaining polynomial local computation for fixed parameters, when comparing the output to the usual domination number.

0.33

Average pairwise Hamming distance of a subset in a hypercube

cs.DM math.COcs.IT ·2026-10-29 ·Yijia Fang, Hao Huang
theory similarity 0.63
Abstract

In this note, we prove that for a subset $\mathcal{F}$ of $\{0,1\}^n$ of density $\frac{1}{8}$, its average pairwise Hamming distance is at least $\frac{n-3}{2}$, with equality attained only by $(n-3)$-dimensional subcubes. This answers a question of Lei Yu, and solves an important open case of a more general question posed by Ahlswede and Katona in 1977.

0.26

Finding Hypercliques Faster Than Brute Force

cs.DS cs.CC ·2026-11-03 ·Josh Alman, Baitian Li, Neha Pant, Kevin Pratt, Ryan Williams
similarity 0.62
Abstract

We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in $O(n^{k-\varepsilon_k})$ time. This refutes the hyperclique conjecture of Lincoln, Vassilevska Williams, and Williams (SODA 2018). Our result follows from the uniform construction of a family of arithmetic circuits of size $O(n^{k-\varepsilon_k})$ for the $k$-hyperclique tensor, a natural higher-order generalization of the matrix multiplication tensor. We obtain two corollaries. First, for every $k$, there exists $\varepsilon > 0$ such that Max-$k$SAT can be solved in $2^{(1-\varepsilon)n} \cdot \mathrm{poly}(m,n)$ time. Second, for every $k$, there exists $\varepsilon > 0$ such that arithmetic progressions of length $k$ in subsets of $\{0,1,\ldots,n\}$ can be detected in $n^{2-\varepsilon}$ time. Both corollaries refute other prominent conjectures in the literature.

0.23

Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences

cs.IT math.CO ·2026-10-26 ·Nader H. Bshouty
theory similarity 0.62
Abstract

Let $d_{K_{s,t}}(n)$ be the largest fraction of all graphs on $[n]$ in a family containing no two distinct members whose symmetric difference is a copy of $K_{s,t}$. We determine this maximum density for every fixed pair of positive integers $s,t$. If both part sizes are odd, it is known that the density is exactly $1/2$. Otherwise, let $2h$ be the largest even part size. We prove $$ d_{K_{s,t}}(n)=Θ_{s,t}(n^{-h}). $$ For $h>1$, this improves the general $O_{s,t}(1/n)$ upper bound obtained from Alon's two-copy gluing theorem~\cite{Alon2024}. The sharp bounds for even stars were already proved by Alon and are recovered as special cases. The upper bound uses the Frankl--Füredi forbidden-intersection theorem. For the lower bound, we construct binary linear codes using BCH codes. When exactly one part size is even, we assign to each edge the sum of the binary vectors assigned to its endpoints. When both part sizes are even, we identify these vectors with elements of a finite field and assign to each edge the product of its endpoint elements. In both cases, every copy of $K_{s,t}$ has a nonzero syndrome.

0.27

Fractional Dichromatic Number and Domination in Tournaments

cs.DM math.CO ·2026-09-28 ·Paul Colinot, Alantha Newman
theory similarity 0.62
Abstract

Bourneuf, Charbit and Thomassé [BCT25] showed that the domination number of a tournament can be bounded as a function of its fractional dichromatic number. The function proved was exponential and the tools were based on VC-dimension. In this paper, we present two new proofs of this theorem. The first proof is based on a reduction to the problem of bounding the domination number of a $(1/2-ε)$-majority tournament, for which [BCT25] and Charikar, Ramakrishnan and Wang [CRW26] gave tight bounds. This proof yields the same exponential bound on the domination number as in [BCT25]. The second proof gives a quasilinear bound for the domination in terms of the fractional dichromatic number. It was obtained via AI and was inspired by the recent book proof of the existence of a Condorcet Winning Set of size five due to Ramakrishnan [Ram26].

0.34

$K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\sqrt{n})$

cs.DM math.CO ·2026-10-31 ·Jonathan Conroy, Hung Le, Jack Spalding-Jamieson
theory similarity 0.61
Abstract

We show that every $K_h$-minor-free graph with $n$ vertices has a balanced separator of size $O(h\sqrt{n})$ for any parameter $h \in \mathbb{N}$, resolving the conjecture posed by Alon, Seymour, and Thomas [AST90] in 1990. The proof is elementary, building on the combinatorial framework by Le [Le26]. A key new idea of the proof is the existence of a short hitting walk on vertex expanders: given $k$ large (not necessarily disjoint) subsets of vertices, there is a walk of length $O(k/ψ(G))$ hitting every subset, where $ψ(G)$ is the vertex expansion. This technical result substantially improves on an analogous lemma by Alon, Seymour, and Thomas [AST90] in an important parameter setting, where the previous lower bound [Kot00] does not apply.

0.49

Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs

cs.CG math.CO ·2026-11-04 ·Guangjian Zhang
theory similarity 0.61
Abstract · 30 pages

We prove Conjecture 4 of Chan, Chang, Gao, Kisfaludi-Bak, Le, and Zheng (SoCG 2026): for every fixed integer $r\ge0$, the radius-$r$ neighbourhoods of a unit-cube graph in $\mathbb{R}^3$ have bounded VC-dimension. Our bound is $2^{2^{O(r)}}$, independent of the number of vertices. The main ingredient is a VC-dimension bound for reachability through arbitrary fixed-length sequences of three-dimensional generalized dominance relations. Its proof uses groups ordered in two coordinates, with neighbouring groups acting as barriers that preserve this invariant when one layer is removed. Combining these bounds with the existing interval-representation framework, we obtain a Las Vegas algorithm that, for every fixed integer $Δ\ge1$, decides whether a graph given by $n$ cube centres has diameter at most $Δ$ in expected $O_Δ(n^{2-\varepsilon_Δ})$ time, for an explicit constant $\varepsilon_Δ>0$. Finally, for every integer $r\ge7$, we construct unit-cube graphs with rational centres whose radius-$r$ neighbourhoods have VC-dimension $Ω(r^3)$.

0.27