## 100 thoughts on “How Many Cops to Catch a Robber? | Infinite Series”

1. pierrecurie says:

The left diagram has girth 5, and every vertex is connected to 3 others, so its cop# >= 3 by theorem stated earlier. Place 1 lazy cop at top, 2 more at bottom. The only possible starting places for the robber are the 2 arms of the pentagram. Top cop moves down to close off the robber's only exit (eg if robber started on right, cop moves left). Now that the robber is trapped, the best he can do is wait for the inevitable – the cop grabs him in 2 more turns. Since 3 >= lazy cop# >= cop# >= 3, both cop #s are 3.

The right diagram has no pitfalls, so cop# >= 2. Place 2 lazy cops in opposite corners, and 1 in the middle. No matter where the robber starts, he will be caught on the 1st cop move. Alternatively, place 1 regular cop in top right, another in bottom left. Only possible starting place for robber is middle. Top cop moves left, bottom cop moves up. There is nothing the robber can do. Thus, 3 >= lazy cop# >= cop# = 2.

If you think about it, the right diagram is equivalent to rooks on 3×3 chessboard — they can move arbitrarily far horizontally/vertically, but not diagonally. Note that no matter how you arrange 2 rooks, there will be at least 1 hole that they can't reach (at least 1 column they can't cover, at least 1 row they can't cover; intersection is this hole). With lazy cops (ie only 1 rook moves), I strongly suspect that this hole can't move diagonally, so the robber can stay in the hole indefinitely. Thus, I conjecture lazy cop# to be 3.

2. Donald Hobson says:

Pentagram cop 3, lazy cop 3.
Discrete torus cop 2, lazy cop 3.

3. Culmen222 says:

Zugzwang. Always funny to find common german words in science. Zug = move, Zwang = Pressure. Unter Zugzwang setzen = force somebody to decide.

What if the cops consistently fail to recognise the robber because he is rich and the function of the police is to protect his personal property?

5. TimeMasterII says:

could you try a cardioid made of lines?

6. robert jencks says:

I was going to bring up the research team looking at this topic at my university but then they mentioned Professor Sullivan right at the end. Pretty cool.

7. Josh says:

Does the result on upper bounds of cop number for a planar graph have anything to do with the 4 color theorem?

8. Mitchell McGill says:

More game theory!

9. Alexander F says:

If a totally connected graph has uncountably many nodes can the cop win if they don't accept the axiom of choice?

10. Ejo-Bo Sholeh says:

Are infinite graph is like infinite chess??

11. Andreas Grothusheitkamp says:

5:01 Cops has no Timemachinse => 4D Doctor Wins… Troll
6:18 in the infinite line it's infinite Cicles so the Rober Wins… Math… Troll
8:11 I think intuitive NOT Calculated Pentagon 2/4 Square 2 / 3 Pleas correct me
8:40 Zugzwang is a german word (and pronaunced vary wrong) and more importent for Mühle "Nine Men's Morris" then Chess

12. Ali Veli says:

what is cup number of bipartite graphs, can it be 2 or 4 or arbitrarily large?

13. Jason Kehrberg says:

What if the cop and/or robber followed a quantum walk, such as the path of an exciton in photosynthesis?

14. Spyx84 says:

Also in the last episode I immediatly thought of this board game: https://en.wikipedia.org/wiki/Scotland_Yard_(board_game). Anybody know it?

15. Étienne Massé says:

Why do you have quantum physics equation in the background at the end?

I can prove that it needs a non-deterministic Turing Machine with polynomial bounded working memory to know if k cops can get the robber. Thus this is a R-class problem, not a RE-class. It might be easier than R, but I have no proof of it yet

17. Ralph Strocchia says:

I never took a class in graph theory. Do planar graphs have to be finite? You can easily construct an infinite graph that is robber win for any number of cops. You make it like a fractal, where you start with a single cycle. Then for each point on the first cycle, they all branch out into disjoint cycles. The pattern continues, and for any number of cops, the robber just has to pick a cycle far enough down so that the cops can never reach him.

18. Impretzive says:

But what if the cops are the crooks

19. Ko_Zilek says:

Are we going to do higher dimensional cops and robbers; It seems almost kinda mandatory at this point; But I can already tell it will be pretty similar, or well actually you could just flatten the skeleton of the 3D shape onto a 2D plane… thus any dimension; Just keep flatting it until it's 2D.
Nevermind.

20. Drunk in a Dark Room says:

did all the hosts go to the same hand expression classes??? or are you all related??

Can someone explain how the house graph near the end is a cop win in the active variant?

I think an interesting variant to explore would be where any of the cops could arbitrarily be misaligned with the other cops. That is, how many cops n are required for a graph to guarantee that any of the distinct n are able to catch the robber. I would presume under this variant, a misaligned cop would be unknown and would behave optimally for a true cop but would not move to capture a robber on an adjacent vertex. Of course, then this may inform the robber and other cops which cop/s is/are misaligned, which could change their strategy in the middle of the pursuit… Thinking of trying to solve this mathematically seems complicated lol

23. Ares Galamatis says:

@6:30 Hey! If the robber chooses "the infinite" branch, it will take him infinite turns to get caught, in other words that would be never/undefined/etc… or am I missing something?

24. So ein Spast says:

The Robber knows where he is at all times. He knows this because he knows where he isn't. By subtracting where he is from where he isn't or where he isn't from where he is, whichever is greater, he obtains a difference, or deviation…

25. Scott Smith says:

On the infinity tree, it does not matter where the cop start, the cop will win, being at the base is only for the quickest capture no matter where the robber begins.

26. BertiferousRex says:

The surveillance version is like the Clue Museum Caper game…

27. photosinensis says:

Now here's one: Multi-pole variants of the Towers of Hanoi.

Another variant. Suppose we replace the cop with a mad bomber. The bomber wants to blow up an arbitrary point on a graph. However, the bomber must remain on the point for at least n turns to succeed. The bomber will win if there exists a move that will allow him to do this. The cops will win if either they capture the bomber our can prevent the bomber for an arbitrarily long time from setting the bomb.

3, I believe, on any planar graph.

30. Abd Al Rahman says:

Oi…. beauty don't talk about criminals

31. Jakub Mintal says:

About an infinity tree graph: What if the robber chose last branch. Isn't that branch infinitely long? Doesn't it take infinitely many time to a cop to catch a robber? Will immortal cop EVER catch robber?

6:21 That graph has -1/12 vertices

33. sugarfrosted says:

A colleague of mine did her thesis on cops and robbers on infinite graphs. It's a bit technical, but interesting. She deals with things like how hard it is for the robber to find a winning strategy in a cop win graph. The definition she uses is that if the robber can evade capture forever, he wins. http://opencommons.uconn.edu/dissertations/1463/

34. Levi Poon says:

Can we define a doomsday clock for the robber in infinite graphs (similar to that mentioned in the infinite chess video) and if yes, are there graphs with a doomsday clock of omega^2 or higher?

35. Kyto says:

Where can I find the music used on these videos? Love the song at the beginning.

36. shivaram kratos says:

It seems like cop number of graph is always less than chromatic number of graph

37. Francisco Tomi says:

If the branch is infinitely long, then how could it be Cop Number 1? The robber would always be 1 step ahead. It's like the cycle one right?

38. Clayton Coe says:

Interestingly, the ad I was shown before this video said "math sucks".

39. catman64k says:

ummm, now i want to play this:

https://en.wikipedia.org/wiki/Scotland_Yard_(board_game)

40. Abi Gail says:

Another variant it to have edges which can only be traversed by either cops or robbers. Or a variant where you cannot immediately move back on an edge. Or where n cops may make m moves among them on their turn (if m == 1, we have lazy cops). You can also have variants where you have more than 1 robber, and all robbers must be captured at the same time.

41. Xyzzyx says:

Cop number and lazy cop number is 3 for the first. Cop number and lazy cop number is 2 for the second.

42. Iwer Sonsch says:

Dangit, forgot to sub so I missed this video.

43. Derrick White says:

The Peterson Graph! No!!!!!!

44. Johan Richter says:

Very nice video. In the imperfect information version, I think there could be several definitions of the cop number but if we define it as the number of cops needed to win with probability 1 eventually, I think I can show that it is never larger than the usual cop number. Basically, if the cops have a winning strategy for the perfect information game, I think they can win the imperfect information game as well by guessing what the robber does. If they guess right they should win within the same time it takes in the perfect information game. If they don't win within that number of moves they just start again by guessing where the robber is and what he is doing. Repeating this enough times they should eventually guess correctly for long enough to catch the robber.

In fact the above reasoning suggest that you might as well only keep the robber ignorant, and let the cops have perfect information, unless you impose a bound on the number of moves before you declare the game ended with a robber win if he is still on the run.

I end this comment by noting that cycles still have cop number greater than 1. With just one cop, the robber remains still until they see a cop when he moves away. Clearly the cop will never win this game.

45. Johan Richter says:

I can think of several more variations of the game: In the imperfect information version you could force each cop to move independently because they can't share information.

In the original version you could designate a hide-out vertex and the robber wins if he reaches that vertex when a police is not there. The cop number in this version is a most 1 more than in the normal version since a cop could just be stationed at the hide-out but in some graphs it won't increase at all.

Finally there is American Cops and Robbers, where the police just shoot the robber instead of chasing him.

46. Karl Young says:

Seems like an interesting variant would be to give the Graphtopia PD a limited budget such that the cop could only play for n moves – then a question would be for a given cop win graph is there a strategy for the robber to outlast the cop (complicated I guess because it would depend on starting positions…)

47. Emerald Element says:

How would the cop number be affected if the robber was able to move k times on his turn?

48. rav ernot says:

Graphtopia's police department is not very diverse.

49. squirrel fight says:

These people create genocide

50. rahul kumar says:

i'm going to give you a problem, solve it if you can ,if p(n)=nth prime, then prove that for arbitrary large n , p(n+2)-p(n)>=6, this means that for arbitrary large n p(n+2)-p(n) can't be less than 6, p(n+3)-p(n)>=8, p(n+4)-p(n)>=12 ,.. and so on , i can prove that

51. Shakes McTremens says:

Hey, speaking of tree… it's a little Numberphile-y, but is there any chance you could do a video on Tree 3? Nobody else is touching it, and I haven't found anything lay enough to get even the foggiest notion.

52. aspie96 says:

The infinite graph thing is wrong.
The thing is, the assumption is always that they are using the optimal strategy.
The robber does not have an optimal strategy, since whatever decision he makes, there are infinite others that could have given him a longer time before being cought.

53. Jerry Stamos says:

You still did not explain where there is information not known by both but that can be discovered by the other one

54. hellsingmongrel says:

This is basically an explanation of the mechanics behind the board game "Scotland Yard." Fun game, but it can be SUPER HARD!

55. ParmuTownley ; says:

Can you start a math of neural nets series? 🙂

56. Valdagast says:

Does this change if we play the game in more than two dimensions?

57. Humberto Vanegas says:

Hi, one question, in the case of a infinite branched tree would it have one branch with infinite nodes and in this case the robber would be chased infinitely but just in this branch ?

58. Антоша Пушкин says:

That tree at 6:20 looks like its size is -1/12

59. You Juhwan says:

6:34 How can Thief caught if he chose to ran into the infinite branch? then cop can't caught him

60. YonicStudios says:

Here's a realistic variant: Both cop and robber have stamina with a maximum of n, and when they don't move, they recover it fully. When their current stamina is 0, they must stop to recover stamina to their max.

61. Snakemasterepic says:

62. Ted Percival says:

I've heard of a hypercube; now I think I know what one is. Perhaps you could do an entire video on hypercubes — if they're sufficiently interesting or useful.

63. Common Cool Channel says:

How about robbers working in concert?

65. Edward Vogel says:

Seems like the graph theory used here could be applied to search and sorting algorithms to shorten computation times. Can you suggest any further reading? (Preferably for the not good at reading set theoretic notation and has lots of pictures and analogies). Thanks!

66. 334harsan says:

Why not you add a twist: you can only move 1 cop per turn

67. Patrick Demko says:

6:32 Why does he have to start on one of the finite branches? There's no rule about it. Can't he start on the infinityth point on the infinityth branch branches, and never get caught?

68. GD Pokecreeper says:

ßS
2 s’s

69. eder corrales says:

This is cool.

70. Mimo Samo says:

Could anyone please tell me what are the practical uses of such theorem? I'm failing to find any except brain sport

71. Gilthans says:

You switched the results on the passive/active on 9:10. The graph is cop win on passive, and robber win on active 🙂

72. FloppingKarp says:

What if the cop can move twice instead of once?
Are there any graphs that the robber can still avoid the cop?

73. Jacob Cain says:

The answer is 3,3 and 2,2

can anyone please explain how cop no. of the 3×3 graph will be 3? And also how to find lazy cop number?
thanks.

75. Levi Willrich says:

couldn't the robber start at the second node of the branch of length ω and survive for ω turns and die of natural causes ω-robber lifetime turns before getting caught

76. h def says:

but what can you use this problem for in real life?

77. h def says:

but what can you use this problem for in real life?

78. Shane Barnes says:

This is my guess(I haven't watched) 2

79. Felix Xu says:

What about to change a lightbulb?

80. Lukas99g says:

5:00 I'll just give you an board that's made out of squares and has a billion contact points

81. Thapelo Mokoto says:

Is a mobile game for this?

82. densch123 says:

the way you say it, "Zugzwang" sounds like a chinese word.

When in fact it's german!

83. Aaron Baker says:

what if there is multiple robbers and the ability to break others free and there's dual graphs

84. krebul says:

Why am I more concerned with rooting for the robber than understanding the theorem?

85. Tomas Vicek says:

Is there any game on google play or on desktop, where you could move cops or robber on the graph?

86. Ayan Chavan says:

Here's my version with 4 NEW rules:
Rule #1:
For a graph with a positive number of vertices, the number of numbers (x) in a game cane be:
0 <= x <= v – 2 <= 9
for a graph with 11 vertices or less
where "v" is the number of vertices

Rule #2:
If any non-number player lands on a vertex already occupied by a number, that number and ONLY that number is out,
The game is called "reduced" if all the numbers are out.

Rule #3:
There can only be three numbers or less if the graph is infinite.

Rule #4:
The numbers in the game are consecutive and positive numbers.

87. Ayan Chavan says:

(2 + 2)^2 th

88. Jorun Holm says:

Batel cops and robers ther is more robers than police the police is ilimenated you

89. Jorun Holm says:

Make a video on it pleeeeeeaaaaaaassss

90. Jorun Holm says:

Kloark robers and cops. Kloark under grund, police cant go ther, capsel conekt City (normal graph) with kloark graph

91. Jorun Holm says:

An runtrugh of it plleaaaaaaeeeeeeessssss

92. Jorun Holm says:

Of cops and rober, inprfekt information

93. michael roberts says:

Why are all the cops white women and the robber a white man? Are there no lady robbers? Or male cops?

94. Jorun Holm says:

95. vanthursday says:

2. A Good cop and a bad cop xD

96. John Batchler says:

Robber wins play it in real life with the fbi

97. John Batchler says:

It took one cop to break up the FBI criminals

98. Arjun siva says:

If i had a math teacher like her I would've become a math professor.I luv her sooo much

99. T. says: