13
$\begingroup$

Cops & Robbers is a certain pursuit-evasion game between two players, Alice and Bob. Alice is in charge of the Justice Bureau, which controls one or more law enforcement officers, the cops. Bob controls a single robber, a guy whose main concern is to evade the cops at any costs. Both deploy their guys on the vertices of a city, a simple graph, and start a manhunt under the following natural rules:

  • On her turn, Alice chooses a (possibly empty) subset of the cops and moves them to some adjacent vertices.

  • On his turn, Bob may either move his robber to an adjacent vertex or stay still.

  • The game ends with a win for Alice whenever any of her cops manages to occupy the same vertex as the robber. Bob wins if this never happens in the game.

Cops & Robbers and its variants have been studied on finite graphs so extensively, while little is known in the case of the infinite graphs, particularly those of uncountable cardinality which are the subject of this question. One may take a look at the following references for a fairly comprehensive account of the topic (including some results concerning the infinite version) or watch this and this episodes of PBS Infinite Series show by Kelsey Houston-Edwards:

The cop number of a graph is the minimum number of the cops that Alice needs to have a winning strategy in the game. A graph with cop number $1$ is called cop-win. Otherwise, it is called robber-win. Before getting into the main question, let's observe that the cop number of a large infinite graph may or may not be large. For instance, $K_{\kappa}$ and $S_{\kappa}$, the complete and star graph of size $\kappa$, are clearly cop-win and therefore have the cop number $1$. In contrary, the totally disconnected graph of size $\kappa$ has the cop number $\kappa$. Some other examples are the infinite path $P_{\infty}$, and Rado graph, $\mathcal{R}$, which have the cop number $\aleph_0$.

Definition. We call connected infinite graphs with minimum and maximum possible cop-numbers (i.e. $1$ and $|G|$), law and crime neighborhoods respectively. A Mega City is an infinite connected graph, $M$, with the "dystopian" property that $M$ contains either a law or a crime neighborhood as big as $|M|$ as its sub-graph. An uncountable cardinal $\kappa$ is a Dredd cardinal (named after Judge Dredd) if every connected graph of size $\kappa$ is a Mega City.

The first question is about the possible large cardinal strength of the existence of such a Ramsey-like cardinal.

Question 1. Is there any Dredd cardinal? What is their large cardinal strength in comparison with other large cardinals of some Ramsey characterization such as weakly compact, Erdős, and Ramsey cardinals?

Remark 1. An approach towards question 1 might be through considering $\kappa$-Aronszajn trees and checking the tree property which provides a characterization of weakly compact cardinals. Maybe one can relate the cofinal branches in a $\kappa$-tree to the law or crime neighborhoods in a Mega City of size $\kappa$, given the fact that trees and paths are rather simple cities to analyze for the game of cops and robbers. Also, as Will mentioned in his comments here and here, in the definition of a Mega-City the connectedness assumption is essential for the whole graph and crime neighborhoods in order to avoid easy constructions.

The next question is about the possible characterization of infinite connected graphs with arbitrary cop-numbers.

Question 2. Let $\kappa$ be an infinite cardinal and $1\leq \lambda\leq \kappa$. Is there a connected graph of size $\kappa$ and cop number $\lambda$? How many graphs of this type are there up to isomorphism (for any given $\kappa$, $\lambda$)?

Remark 2. Concerning the question 2 in the special cases such as $\kappa=2^{\aleph_0}$, an approach could be thinking about using cardinal characteristics of the continuum for constructing examples of connected (directed) graphs of size continuum with cop numbers strictly less than $2^{\aleph_0}$. In order to observe this, note that cop number of any graph is less than or equal to its domination number because one may catch the robber in the first move simply by deploying one cop on each vertex in a minimal dominating set of the graph. The idea is that the set-theoretic dominating number, $\mathfrak{d}$, serves as the domination number of a graph, $G$, of size $2^{\aleph_{0}}$ (don't confuse the similar terms in set theory and graph theory with each other). At the request of Monroe, let me clarify the example a little bit more:

$G$ is defined by the sequence domination relation between reals (i.e. functions $f:\omega\rightarrow \omega$). In this graph, the vertex labeled by $g$ is adjacent to $f$ (i.e. $g\rightarrow f$) if $g$ dominates $f$ as a sequence (denoted by $f\leq^* g$) that is $f(n)\leq g(n)$ for all but finitely many $n\in \omega$. Now a dominating family, $\mathcal{F}$, of sequences for the entire real numbers is a set of functions from $\omega $ to $\omega$ such that every such function is either in $\mathcal{F}$ or is $\leq^*$-dominated by a member of $\mathcal{F}$ (i.e. $\mathcal{F}$ is a domination set of $G$ in the graph-theoretic sense) and $\mathfrak{d}$ is defined to be the minimum size of such a family (i.e. the domination number of the graph $G$). Consequently we have $c(G)\leq \mathfrak{d}\leq 2^{\aleph_0}$ (which $c(G)$ stands for the cop number of $G$). Finally using forcing one may make $\mathfrak{d}<2^{\aleph_0}$ and so the cop number of the graph $G$ in the generic extension will be strictly smaller than $2^{\aleph_{0}}$.

However, one should note that generally, the domination number is a very loose upper bound for the cop number of a graph. (Certainly, the Justice Bureau has much more clever strategies to control the crime rate in the city rather than placing a cop right in the front of every single home!) For instance, the domination number of the dodecahedron graph (of size $20$) is $7$ while its cop-number is only $3$. Here, the following question arises:

Question 3. What is the cop-number of $G$, the sequence domination graph of size continuum described in the previous remark? Can it be countable? If not, what is the precise value of this new cardinal characteristic of continuum and how does it relate to the other entities in the Cichoń's diagram?

$\endgroup$
24
  • 8
    $\begingroup$ I have no idea how to answer your questions, but I have to say, they were definitely fun to read. $\endgroup$
    – Gro-Tsen
    Jun 3, 2018 at 17:23
  • 2
    $\begingroup$ @Gro-Tsen That is very kind of you, David! Glad to hear that you like my question composing style on MathOverflow. :-) $\endgroup$ Jun 3, 2018 at 17:27
  • 2
    $\begingroup$ I thought it was going to be cops and robbers in the Vatican! $\endgroup$ Jun 3, 2018 at 20:19
  • 3
    $\begingroup$ @HarryGindi A multi-factional version of the game may involve a Batman character who possesses special abilities (e.g. speed). His aim is to catch the robber while avoiding the cops all the time.Batman wins if he catches the robber before the cops. In this sense, the corresponding ultimate dystopian city will be Gotham and we may end-up defining a Batman cardinal and a Joker anti-large cardinal principle that holds in a Harley Quinn model! ;-P $\endgroup$ Jun 3, 2018 at 21:10
  • 1
    $\begingroup$ A possibly stupid question: Do you know of any infinite graphs that are not "mega-cities"? $\endgroup$
    – Will Brian
    Jun 4, 2018 at 12:43

3 Answers 3

7
$\begingroup$

Every uncountable regular cardinal is a Dredd cardinal.

For suppose $\kappa$ is an uncountable regular cardinal, and let $G$ be a connected graph on $\kappa$ vertices.

Lemma: $G$ has a vertex of degree $\kappa$.

Proof of Lemma: Aiming for a contradiction, suppose this is not the case. Fix some vertex $v_0$ of $G$, and let $V_0 = \{v_0\}$. Inductively define sets $V_1,V_2,V_3\dots$ of vertices of $G$ so that $$V_{n+1} = V_n \cup \{v : v \text{ is adjacent to some vertex in } V_n\}.$$ By induction (using the regularity of $\kappa$ at each step), one may show that $|V_n| < \kappa$ for each $n$. On the one hand, this implies that $|\bigcup_{n < \omega}V_n| < \kappa$ (because $\kappa$ is regular and uncountable). On the other hand, $\bigcup_{n < \omega}V_n$ is the connected component of $G$ containing $v_0$. This shows that $G$ is not connected, contrary to our assumption. QED

Let $v$ be a vertex of $G$ with degree $\kappa$. Then $G$ has a size-$\kappa$ "law" neighborhood, namely the subgraph formed by $v$ together with all of its neighbors. (This is a law neighborhood because the cops have a simple winning strategy: place an officer at $v$, and then capture the robber in their next move!) QED

This shows that there are plenty of Dredd cardinals, and no large cardinal axioms are necessary to find them, answering question 1.

$\endgroup$
1
  • $\begingroup$ (+1) Nice argument! Thank you, Will! Though, I still suspect that during playing the game of cops and robbers on infinite graphs, some Ramsey-theoretic large cardinals may appear out of the blue! Anyway, just like tree property, the nature of the theory is somehow open to the involvement of large cardinals which might be lurking in the background. I will be happy to hear if anyone finds a natural connection between such games on infinite graphs and large cardinals. Ultimately, following this approach, some game theoretic characterization of large cardinals might be not that out of reach. $\endgroup$ Jun 4, 2018 at 20:57
4
$\begingroup$

Here is an answer to question 2. First note that it suffices to consider the case where $\lambda=\kappa.$

For regular $\kappa,$ you may consider the following graph:

enter image description here

The point is that given less than $\kappa$-many points on the graph, there exists a line on which there are no points, except possibly on the center.

Similar idea works for singular cardinals, using the following graph. Here $\lambda = cf(\kappa)$ and $(\kappa_\xi: \xi< \lambda)$ is an increasing sequence of regular cardinals cofinal in $\kappa:$

enter image description here

$\endgroup$
1
  • $\begingroup$ Thanks for your answer, Mohammad! I think by adding enough so-called pitfalls (which actually don't change the cop number of a graph) to your examples one may obtain graphs of size $\kappa$ and cop number $\lambda$ for any infinite cardinals $\kappa, \lambda$. $\endgroup$ Jul 14, 2018 at 4:21
2
$\begingroup$

Here is an attempt at answering Question 2:

Start with a graph $H$ with cop number $\lambda$. If $\lambda$ is finite, then there is a finite such graph (e.g. by Theorem 1.1 in this paper) for infinite $\lambda$ this can be $\lambda$ rays with a common starting point. Then attach $\kappa$ many leaves to any vertex $v_0$ of $H$ to obtain a graph $G$.

The resulting graph obviously has $\kappa$ vertices (we'd have to be more careful to say something about finite $\kappa$ though).

To see that $G$ has cop number at most $\lambda$, observe that the cops can play the same strategy on $G$ as on $H$ (if the robber moves to one of the new leaves, then they just pretend that he's at $v_0$ instead). When the game on $H$ ends, then either the robber is captured, or he is at one of the new leaves with a cop positioned at $v_0$ (and hence he will be captured in the next move).

To show that the cop number of $G$ is at least $\lambda$, observe that the robber can play a winning strategy against any smaller number of cops on $H$ (and pretend that cops that have moved to new leaves are at $v_0$).

As for the number of nonisomorphic examples: in the arguments above it was not essential that $G - H$ is edgeless, in fact we can take any graph on $\kappa$ vertices and connect all of its vertices to $v_0$ and the same argument still goes through.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.