Timeline for Cops, Robbers and Cardinals: The Infinite Manhunt
Current License: CC BY-SA 4.0
44 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 16, 2019 at 12:00 | review | Close votes | |||
| Apr 16, 2019 at 18:58 | |||||
| Jul 14, 2018 at 3:29 | review | Close votes | |||
| Jul 14, 2018 at 17:35 | |||||
| Jul 14, 2018 at 3:07 | answer | added | Mohammad Golshani | timeline score: 4 | |
| Jun 5, 2018 at 20:30 | answer | added | Florian Lehner | timeline score: 2 | |
| Jun 5, 2018 at 19:29 | comment | added | Isky Mathews | Could there be a graph such that it is not cop-win in ZFC but is cop-win in some forcing-extension? | |
| Jun 5, 2018 at 15:16 | comment | added | Morteza Azad | @Goldstern Yes, Martin! I By "sub-graph" I literally mean vertex-induced subgraph. | |
| Jun 5, 2018 at 14:53 | comment | added | Goldstern | When you write "sub-graph", do you mean induced subgraph? | |
| Jun 5, 2018 at 7:42 | comment | added | Morteza Azad | @Gro-Tsen The answers to this interesting old question of Bill Thurston might be of your interest too. It is related to some mathematicians' (often personal) imaginative approach towards serious mathematical stuff. I think it is a generally useful (or at least harmless) practice to share some of these weird personal descriptions of the math problems publicly. It helps people get more involved in the collective effort for finding a solution as well as encouraging them to establish their own imaginative approaches. | |
| Jun 4, 2018 at 22:09 | history | edited | Morteza Azad | CC BY-SA 4.0 |
deleted 1 character in body
|
| Jun 4, 2018 at 22:07 | comment | added | Morteza Azad | @JoelDavidHamkins Added in order to make the post self-contained! :-) I preferred to exclude the rules of the game in the original post (and add a Wikipedia link instead) because I thought it might be quite well-known for many. And as you may have guessed, I have been a little bit concerned with the extraordinary length of the question (which eventually got even longer due to implementing colleagues' useful suggestions in the comments). | |
| Jun 4, 2018 at 21:59 | history | edited | Morteza Azad | CC BY-SA 4.0 |
added 361 characters in body
|
| Jun 4, 2018 at 21:34 | comment | added | Joel David Hamkins | The post is very long, but you don't explain the rules of the game? | |
| Jun 4, 2018 at 21:10 | history | edited | Morteza Azad | CC BY-SA 4.0 |
deleted 344 characters in body
|
| Jun 4, 2018 at 21:05 | history | edited | Morteza Azad | CC BY-SA 4.0 |
deleted 344 characters in body
|
| Jun 4, 2018 at 19:33 | answer | added | Will Brian | timeline score: 7 | |
| Jun 4, 2018 at 18:28 | comment | added | Goldstern | @WillBrian Thank you, you are right. I confused law/crime with cliques/anticliques. | |
| Jun 4, 2018 at 18:13 | comment | added | Morteza Azad | @WillBrian However, it wasn't mentioned explicitly but in the new definition, we require everything (including Mega City and its crime neighborhoods) to be connected. This matches the intuitive description of a city/neighborhood better. I edited the definition in order to avoid ambiguity. Thanks for the subtle correction, Will! | |
| Jun 4, 2018 at 18:08 | history | edited | Morteza Azad | CC BY-SA 4.0 |
added 243 characters in body
|
| Jun 4, 2018 at 17:51 | comment | added | Will Brian | On second thought, your new definition of a Dredd cardinal makes no sense to me. If you require law/crime neighborhoods to be connected, then the edgeless graph is an easy example of a graph on $\kappa$ vertices with no law/crime neighborhoods of size $\kappa$. So there are no Dredd cardinals, but for trivial reasons. Did you intend something different with the new definition? | |
| Jun 4, 2018 at 17:31 | comment | added | Will Brian | Regarding the new version of question 1, let me point out that Dredd cardinals must be singular. For if $\kappa$ is regular and $G$ is a graph of size $\kappa$, then either $(1)$ there is a vertex of degree $\kappa$, and the subgraph consisting of that vertex and its neighbors is a "law" neighborhood of size $\kappa$, or $(2)$ there is no vertex of degree $\kappa$, in which case the regularity of $\kappa$ implies there are no connected neighborhoods of size $\kappa$. | |
| Jun 4, 2018 at 16:50 | history | edited | Morteza Azad | CC BY-SA 4.0 |
added 915 characters in body
|
| Jun 4, 2018 at 15:34 | comment | added | Monroe Eskew | It was confusing because all of the previous discussion was about undirected graphs. | |
| Jun 4, 2018 at 15:24 | comment | added | Morteza Azad | @MonroeEskew No. I actually mean the directed graph, $G$, to be formed in the opposite direction that you mentioned in your comment. (I edited the typo in the remark to make this point clear). In this sense, the vertex labeled by the constant $0$ sequence is just a dead end. Placing a cop on that vertex would be just a waste of manpower simply because everybody can go into this vertex but nobody can come out; a black hole! | |
| Jun 4, 2018 at 15:19 | history | edited | Morteza Azad | CC BY-SA 4.0 |
deleted 91 characters in body
|
| Jun 4, 2018 at 14:29 | comment | added | Monroe Eskew | The domination number of the graph you defined is 1, since every real is adjacent to the constant 0 function. | |
| Jun 4, 2018 at 14:00 | comment | added | Morteza Azad | @WillBrian Hmmm... Sounds correct! So in order to avoid triviality, one may need to add the connectedness requirement for the crime neighborhoods in the definition of a Mega City. Note that $P_{\infty}$ and Rado graph, $R$, are true examples of connected countable crime neighborhoods and the soul of the question is actually about such creatures to exist as the sub-graph of $M$. | |
| Jun 4, 2018 at 13:44 | comment | added | Morteza Azad | @MonroeEskew I added some extra explanations to the original post. Hope the approach described in the remark 2 is more clear now. | |
| Jun 4, 2018 at 13:43 | history | edited | Morteza Azad | CC BY-SA 4.0 |
added 1137 characters in body
|
| Jun 4, 2018 at 13:22 | comment | added | Will Brian | Shouldn't every regular cardinal be a Dredd cardinal? Suppose we are given a graph of regular size $\kappa$. Either there is a vertex of degree $\kappa$, in which case the subgraph consisting of that vertex and its neighbors is a "law" neighborhood of size $\kappa$, or there is no vertex of degree $\kappa$, and we can recursively construct an edgeless subgraph of size $\kappa$ (using the regularity of $\kappa$) to find a large "crime" neighborhood. Am I missing something? | |
| Jun 4, 2018 at 13:06 | comment | added | Will Brian | @Goldstern: I don't think that example works. The graph you're describing has a size-$\aleph_1$ subgraph with cop number $1$, namely the graph on the reals in $[x_0,\infty)$. (The cop number of this subgraph is $1$, because it has a vertex, namely $x_0$, connected to every other vertex in the graph, so the cops can win by placing a single officer there.) If I understand the definitions correctly, this makes the original graph a mega-city. | |
| Jun 4, 2018 at 13:01 | comment | added | Goldstern | @WillBrian A classical example (but the name of its inventor escapes me at the moment): Let $(x_i:i<\omega_1)$ be a 1-1 sequence of reals. Define a graph on $\omega_1$ by connecting $i$ and $j$ if and only if "$i<j \Leftrightarrow x_i<x_j$" holds, where the first order is between ordinals, the second between real numbers. This graph is uncountable but all "crime" neighborhoods and all "law" neighborhoods are countable (otherwise you would get an increasing or decreasing $\omega_1$-sequence of reals). | |
| Jun 4, 2018 at 12:43 | comment | added | Will Brian | A possibly stupid question: Do you know of any infinite graphs that are not "mega-cities"? | |
| Jun 4, 2018 at 11:06 | comment | added | Monroe Eskew | I don't understand your example in Remark 2. When are two reals adjacent? | |
| Jun 4, 2018 at 7:47 | history | edited | Morteza Azad | CC BY-SA 4.0 |
added 228 characters in body
|
| Jun 4, 2018 at 0:35 | review | Close votes | |||
| Jun 4, 2018 at 7:54 | |||||
| Jun 3, 2018 at 21:10 | comment | added | Morteza Azad | @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 | |
| Jun 3, 2018 at 20:41 | history | edited | Morteza Azad | CC BY-SA 4.0 |
deleted 5 characters in body
|
| Jun 3, 2018 at 20:19 | comment | added | Harry Gindi | I thought it was going to be cops and robbers in the Vatican! | |
| Jun 3, 2018 at 20:05 | history | edited | Morteza Azad | CC BY-SA 4.0 |
added 22 characters in body
|
| Jun 3, 2018 at 18:35 | history | edited | Morteza Azad | CC BY-SA 4.0 |
deleted 10 characters in body
|
| Jun 3, 2018 at 17:27 | comment | added | Morteza Azad | @Gro-Tsen That is very kind of you, David! Glad to hear that you like my question composing style on MathOverflow. :-) | |
| Jun 3, 2018 at 17:23 | comment | added | Gro-Tsen | I have no idea how to answer your questions, but I have to say, they were definitely fun to read. | |
| Jun 3, 2018 at 17:21 | history | edited | Morteza Azad | CC BY-SA 4.0 |
added 4 characters in body
|
| Jun 3, 2018 at 17:13 | history | asked | Morteza Azad | CC BY-SA 4.0 |