Sharpness of ¼g cop-number exponent

Optimality of the exponent 1/4 · arXiv:2005.10849

arXiv Informal medium confidence— first stated 2020-05-21

Authors: Peter Bradshaw, Seyyed Aliasghar Hosseini, Bojan Mohar, Ladislav Stacho

Status open high confidence

The conjecture asks whether the exponent g/4 in the lower bound c(G) ≥ Ω((\delta-1)^{g/4}) is best possible, i.e., whether it can be improved to (1/4+ε)g. No paper has proved or disproved this. Clow (arXiv:2306.00220, 2023) established a matching upper bound c(G) ≤ O(n log n · (\delta-1)^{-⌊(g+1)/4⌋}), showing both bounds carry the same g/4 exponent and providing indirect evidence that 1/4 is optimal, but the conjecture remains open.

Cited literature (1)

partial Graphs with Large Girth and Small Cop Number (2023)

Alexander Clow · arXiv preprint · arXiv:2306.00220

Proves c(G) ≤ 6n log(n)/(\delta-1)^{⌊(g+1)/4⌋} for graphs of girth g and minimum degree δ ≥ 2, matching the 1/4 exponent of the Bradshaw–Hosseini–Mohar–Stacho lower bound; poses Conjecture 1.4 that the optimal cop number scales as (\delta-1)^{(1+o(1))g/4} but does not resolve whether the lower-bound exponent can be improved to (1/4+ε)g.

Reviewer notes. The Clow paper (arXiv:2306.00220) shows that both the lower and upper bounds on cop number for graphs of girth g and min degree δ carry the same 1/4 exponent, lending structural support to the conjecture that 1/4 is optimal. The source paper also proves via Ramanujan graphs that the true exponent cannot exceed 3/8. Whether the lower bound can be sharpened to (1/4+ε)g remains open; no counterexample or proof has been found in the literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Is the coefficient $\frac{1}{4}$ of $g$ in the lower bound $\Omega\!\left((\delta-1)^{g/4}\right)$ for the cop number of graphs of girth $g$ and minimum degree $\delta$ best possible, i.e., can the exponent be improved to $\left(\frac{1}{4}+\varepsilon\right)g$ for some $\varepsilon > 0$?

Context

Immediately after stating Theorem 1.1, the authors note: 'One may naturally ask if the coefficient $\frac{1}{4}$ of $g$ is best possible. While we do not have an answer to this question …'. They exhibit conditional evidence (via Meyniel's conjecture and Conjecture 1.3) that $\frac{1}{4}$ is optimal, and also prove via Ramanujan graphs that the true exponent cannot exceed $\frac{3}{8}$.

Notes. Stated as prose without a labelled environment; the abstract frames it as 'several reasons for conjecturing that the exponent $\frac{1}{4}g$ cannot be improved to $(\frac{1}{4}+\varepsilon)g$'.

Source paper

On the cop number of graphs of high girth
Peter Bradshaw, Seyyed Aliasghar Hosseini, Bojan Mohar, Ladislav Stacho · 2020-05-21
https://arxiv.org/abs/2005.10849 PDF source