论文标题
警察和强盗游戏的粗糙几何形状
Coarse geometry of the Cops and robber game
论文作者
论文摘要
我们在图表上介绍了警察和强盗游戏的两个变体。这些游戏在$ \ mathbb {z} _+\ cup \ {\ infty \} $中产生两个不变性，对于任何连接的图形$γ$，{弱cop $ \ mathsf {wcop}（wcop}（γ）$}和{强Cop $ $ \ m \ m scop {scop {scop} $}。这些不变的人满足了$ \ mathsf {scop}（γ）\ leq \ mathsf {wcop}（γ）$。任何有限或树的图形都具有强大的COP第一。这些新的不变剂保存在图形的小局部扰动下，具体来说，弱和强的COP数字都是连接图的准iSmotem ibotic不变性。更笼统地，我们证明，如果$δ$是$γ$的准重取，那么$ \ mathsf {wcop}（δ）\ leq \ mathsf {wcop}（wcop}（γ）$和$ \ mathsf {scop}（scop}（Δ）（δ）我们展示了任意弱的COP数字的图示例（分别为强COP数）。我们证明双曲线图具有强大的COP第一。我们还证明，单端的不符合局部的顶点传播图具有无限的COP数量。我们提出了一个问题，即是否存在有限的弱（分别强）COP数字的连接的顶点及其图形。
We introduce two variations of the cops and robber game on graphs. These games yield two invariants in $\mathbb{Z}_+\cup\{\infty\}$ for any connected graph $Γ$, the {weak cop number $\mathsf{wcop}(Γ)$} and the {strong cop number $\mathsf{scop}(Γ)$}. These invariants satisfy that $\mathsf{scop}(Γ)\leq\mathsf{wcop}(Γ)$. Any graph that is finite or a tree has strong cop number one. These new invariants are preserved under small local perturbations of the graph, specifically, both the weak and strong cop numbers are quasi-isometric invariants of connected graphs. More generally, we prove that if $Δ$ is a quasi-retract of $Γ$ then $\mathsf{wcop}(Δ)\leq\mathsf{wcop}(Γ)$ and $\mathsf{scop}(Δ)\leq\mathsf{scop}(Γ)$. We exhibit families of examples of graphs with arbitrary weak cop number (resp. strong cop number). We prove that hyperbolic graphs have strong cop number one. We also prove that one-ended non-amenable locally-finite vertex-transitive graphs have infinite weak cop number. We raise the question of whether there exists a connected vertex transitive graph with finite weak (resp. strong) cop number different than one.
