If movies have taught me anything, it's that you ony ever need two cops: a grizzled loose-cannon veteran of the force and a naive rooky fresh out of the academy. When these two are on the case, that robber will always get caught.

@MegaAwesomeNick

6 жыл бұрын

Unless the veteran cop gets killed and resurrected as a cyborg then it's only one. Your move creep.

@robertjencks3679

6 жыл бұрын

Additionally, movies teach us that cops 2 weeks from retirement should probably stay as far away from the robbers as possible.

@MegaAwesomeNick

6 жыл бұрын

And any cops that are already retired will inevitably get forced "back in the game."

More game theory!

1:10 police department of graphtopia........ What next? Joker department of Gotham city!!!!! *Really nice though.*

@12q8

6 жыл бұрын

It is actually at 1:09

@JanuszGamerX

6 жыл бұрын

KA 237 did you mean 1:08

@12q8

6 жыл бұрын

Nah, I meant 1:08.576873, but I rounded up.

Thanks for making these! They're so good

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

@Sax4565

6 жыл бұрын

the first time I read Eigenvector or Ansatz (like for a differential equation) in a quantum physics book after only learning about those things in German I was quite surprised :D

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.

@brendansullivan1745

6 жыл бұрын

robert jencks 👋

Someone needs to make this a real online game

@Colonies_Dev

Жыл бұрын

that would be kinda boring because we always know the outcome lmao

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.

The game "Scotland Yard"

@henselstep

6 жыл бұрын

It has remind me to that game, too :D

@apteropith

6 жыл бұрын

I've played this.

2:00 - That one lone node on our left is known as 'the hideout'. No cop ever thinks of looking there.

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.

@PeterAuto1

4 жыл бұрын

that's a good point.

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

This is cool.

2. A Good cop and a bad cop xD

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 3x3 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.

@ykl1277

6 жыл бұрын

I will make a prove of your conjecture that the hole can't move diagonally in lazy cop for the right graph. define the vertices as v(i,j) where it is the ith row and jth column. There are 1 hole in the cop coverage. Let that vertice be v(m,n). Moving a cop vertically only change m, and moving a cop horizontally only change n. For the hole to be unreachable by robber, both m and n has to change. Therefore the hole is always reachable by the robber.

@ben8557

6 жыл бұрын

Actually, I believe that the lazy cop number of the right diagram is 2. Place a lazy cop at the center top and center bottom. Then the only place for the robber to go is the center right or center left. then move one of the cops to the right or the left(depending on which side the robber is on). If the robber stays in place then the cop that moved can get the robber. If the robber moves it can only move into a vertex connected to cop vertex. Therefore the lazy cop number of the right diagram is 2.

@pierrecurie

6 жыл бұрын

+benboy25 I The center left/right are connected, so the robber can take that option.

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

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?

@Car-rp8dg

5 жыл бұрын

Levi Poon no that’s over infinity mate !

Without the introduction of loops, the robber could always win in a situation where the map comprises of a line of infinite points - assuming that the robber is placed after the cops. For cop number 10,000, the robber would simply have to place themselves right of the rightmost cop (and the same for the left). If the cops are placed second, then they could simply surround the robber 1 step away in any situation and the cop number for that game would be equal to or lower than the number of vertexes surrounding the point the robber starts on.

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

infinite series channel 2 please, with more detail on the proofs

@SSJProgramming

6 жыл бұрын

I second that

@Radianx001

6 жыл бұрын

YESSSSS I WANT THE MATH

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...)

@spammerspammer530

6 жыл бұрын

there's a parameter called the cop-throttling number that takes into consideration how fast the cops can catch the robber as well; this might be of interest

@isomeme

5 жыл бұрын

The THX-1138 variant. :)

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

The Peterson Graph! No!!!!!!

Reminds me of Pacman!

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...

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.

@PeterAuto1

4 жыл бұрын

but the american cop can only shoot in a straight line

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

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!

@edvogel56

6 жыл бұрын

Turns out there is a book at more or less my reading level also. So I ordered a used copy from Amazon: bookstore.ams.org/stml-61

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

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.

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.

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 ?

6:42 : I choose the last branch.

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.

@sugarfrosted2005

6 жыл бұрын

Depends on your notion of infinite tree. The variant that's usually used allows for branches that aren't infinite. The robber can escape if he is able to find an infinite branch or using the mathematical parlance a "path". This is a fairly interesting problem using this definition, because in almost all such trees (where you can compute the edge relation) the graph is robber win, but there is no way for the robber to compute a winning strategy.

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

@brendansullivan1745

6 жыл бұрын

velcrorex All the proofs I have seen do not make use of the 4 color theorem. I have also wondered if there is some kind of connection, but I'm not aware of any.

6:21 That graph has -1/12 vertices

@dcs_0

6 жыл бұрын

haha was looking for this comment xD

@LineRider0

6 жыл бұрын

technically it's 11/12 vertices because the vertex the cop starts on isn't part of any of the branches

How about robbers working in concert?

@edvogel56

6 жыл бұрын

Lookouts maybe?

An runtrugh of it plleaaaaaaeeeeeeessssss

What about a Cop with a roadblock? How many roadblocks would a Cop need to win? Cops can place a roadblock on an adjacent path instead of moving.

The surveillance version is like the Clue Museum Caper game...

For any chess players, the graph shown at 9:13 is a cop win in the active version of the game due to triangulation! The cop needs to lose a tempo to force the robber into zugzwang.

could you try a cardioid made of lines?

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

Can you start a math of neural nets series? :)

@guitarheroprince123

6 жыл бұрын

Edward Vogel I watch 3blue1brown videos as soon as he uploads :)

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.

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

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

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

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?

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.

@RandomBurfness

6 жыл бұрын

No, planar graphs are not necessarily finite. My personal favourite example of this is if you take your vertices to be the integers on the real number line, and connect two vertices if and only if they differ by 1. So you connect 1 with 0 and 2, -29 with -30 and -28, and so on. This is a planar graph because no edge needs to cross over another edge. But it is decidedly not finite, since there is an infinite amount of integers. If you want something a bit more two-dimensional, consider the same example, but instead make your vertices the integer lattice on R^2, the cartesian product of the real line with itself, and connect two vertices if and only if only one of their coordinates differ by 1. So, for instance, you connect (0, 0) with (-1, 0), (1, 0), (0, 1), and (0, -1); you connect (14, -3) with (15, -3), (13, -3), (14, -4), and (14, -2), etc. This is clearly a planar graph because no edge has to cross over another edge, but it is evidently not finite. You can generalise this example into R^n. The only thing you have to remember is you only connect two vertices if and only if only one of their coordinates differ by 1. There are as such infinitely many of these examples of this type.

@ralphinoful

6 жыл бұрын

But then the graph I constructed certainly doesn't have a cop number of 3 or less. Or maybe I'm thinking of something wrong?

@desertbutterflypic

6 жыл бұрын

That’s only robber-win in the sense that an infinite line of connected points is. o--o--o--… (cops pick their positions, robber picks a position two points to the right of the cop and runs away to the right forever.) Hence 9:25.

@ralphinoful

6 жыл бұрын

Ahh. I missed that. Thanks

It took one cop to break up the FBI criminals

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. opencommons.uconn.edu/dissertations/1463/

@pbsinfiniteseries

6 жыл бұрын

Thanks for sharing!

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.

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

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

@desertbutterflypic

6 жыл бұрын

Cop starts at the top. Robber can’t be at any of the upper two points, because they will be caught right away, so they’re at one of the bottom two points. Cop moves to the upper point on the opposite side of the robber. The robber is now forced to move to a point adjacent to the cop.

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

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

@chemicalbrother5743

6 жыл бұрын

Nice

@GeekyNeil

6 жыл бұрын

Nice thought. I think the answer is yes. The axiom of choice allows an arbitrary element to be chosen from a possibly infinite family of possibly infinite sized sets. In this case, the cop only needs to choose the node which the robber is currently occupying, which is no choice at all.

@travellcriner6849

6 жыл бұрын

I believe it depends on how you phrase the rules of this game. If the cop and robber are both placed on this graph, then -- axiom of choice or not -- the cop can get to the robber since he need only select the (definitely existent!) node containing the robber. However, you'd have a hard time convincing the cop the graph exists in the first place. That's because you'd have to tell him how, given the uncountable, disjoint collection of singleton sets (one per node) you managed to select one from each to construct the graph.

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

You should do Simpson's paradox.

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

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

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.

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

@MikeRosoftJH

6 жыл бұрын

We have a Czech mutation of the game, it is called "Phantom of the old Prague".

@zairaner1489

6 жыл бұрын

yes!!!

To ADD:new ADD (cool)

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

What about to change a lightbulb?

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

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

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

@PeterAuto1

4 жыл бұрын

Understanding Graphs better.

19 cops

Dangit, forgot to sub so I missed this video.

Answer on a cycle: 2

So if you form such a grid on a sphere, increase the nodes to an arbitrarily large number such that the motion of the cops and robber on the surface appears to be free, and give the participants a size compared to the sphere equal to that of one human to the earth what then would the cop number be?

@rmsgrey

6 жыл бұрын

At most 3. Any graph you can draw on a sphere without crossings can also be drawn on a plane.

@franzluggin398

6 жыл бұрын

If you construct it in such a way that the degree of every vertex grows without bound (similar to how you have infinitely many directions to choose from on the surface of a sphere), then I guess it comes down to a geometry problem: Given a big sphere S of radius R and a small sphere s of radius r on the surface of the first sphere with 0

@franzluggin398

6 жыл бұрын

And as it turns out, this N is indeed 3 for every 0

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

@pbsinfiniteseries

6 жыл бұрын

Sometimes ads can be misleading. :)

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

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

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

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

@TheDennisch

6 жыл бұрын

Ali Veli abitrarily large. Here is how to construct a bipartite graph with cop number >= n. Take a finite graph G with cop number at least n (this is possible as shown in the video), with vertecies {1,..,m}. This means the robber has a winning strategy against n cops. Now construct a graph with verticies {1a,.. ,ma,1b,..,mb} and edges {{ia,jb}, for each i,j where {i,j} is an edge of G}. This new graph is bipartite. Also the robber can apply the winning strategy against n cops from G. Edit: My construction could lead to the new graph not being connected. But if this is the case, then G must have already been bipartite, so we can still find a graph.

The answer is 3,3 and 2,2

Of cops and rober, inprfekt information

Is a mobile game for this?

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?

@straaths

6 жыл бұрын

I understand that choosing 'last' thing from infinitely big set can be hard :D That is probabaly the answer...

@zairaner1489

6 жыл бұрын

Exactly, there is no last branch

@RandomBurfness

6 жыл бұрын

If there was a last branch, there would be a finite amount of positive integers since the nth branch has n vertices. But there are infinitely many positive integers, a contradition; hence, there is no last branch.

@straaths

6 жыл бұрын

How will burglar choose infinitely long branch then? How he knows if the chosen branch is infinite? If we label branches by integers which one it is? There is infinitely many integers therefore we can label branches.

@RandomBurfness

6 жыл бұрын

He can't choose an infinitely long branch because there is no infinitely long branch. There are only finitely long branches. But there are infinitely many branches. So if he picks a branch, which he must because the cop always starts at the centre, there are only finitely many vertices on the branch he picked. Therefore, he will be caught, and the graph G is a cop-win.

@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?

@aresgalamatis7022

6 жыл бұрын

Never mind, I got the answer in the last comment question's answer, about the definition of "caught" for this problem being not caught, rather having running away infinitely, like robbers have to... anyway, that's formal vs informal languages for us all to suffer through :p

@desertbutterflypic

6 жыл бұрын

This one doesn’t rely on changing the definition of “caught”. There are infinitely many branches, but no branch is infinitely long, so when the robber decides to start somewhere on the nth branch, n still has to be an integer and the cop will win in at most n turns by starting at the hub.

Make a video on it pleeeeeeaaaaaaassss

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?

@cutecommie

6 жыл бұрын

The only solution to this game is to end the capitalist system which encourages robbery in the first place.

@flip6383

6 жыл бұрын

as if nobody robbed anything in the USSR or nazi Germany....

@jari2018

6 жыл бұрын

true - look at Putin - he really likes to be the rich guy and rich guy rules

@romanski5811

6 жыл бұрын

+Flip35 Because nazi Germany wasn't capitalistic, right?

Are infinite graph is like infinite chess??

ummm, now i want to play this: en.wikipedia.org/wiki/Scotland_Yard_(board_game)

@lenn939

6 жыл бұрын

It’s a good game.

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

@johanrichter2695

6 жыл бұрын

That is not correct. A hypercube graph has chromatic number 2 but as stated in the video can have high cop number.

@shivaramkratos4018

6 жыл бұрын

Johan Richter true didn't thought about that

But what if the cops are the crooks

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

@Schnorzel1337

2 жыл бұрын

Yes if the graph is not connected. For a connected graph you can say the cop and the robber are x steps away from each other at the start. Let the cop run to the original position of the robber and repeat. Every repetition the robber is half the original distance away from the cop.

Are europeans allowed to enter the challenge contest?

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

@jorunholm9060

5 жыл бұрын

Tree dimensenol if you want

@jorunholm9060

5 жыл бұрын

Or multipol 2d graph

Robber wins play it in real life with the fbi

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

Graphtopia's police department is not very diverse.

Dear PBS Infinite Series, Is it possible to make a future episode about the uses of Tetration (hyper-4)? Yours faithfully, Erik de Wilde

@Platanov

6 жыл бұрын

OMG yes please do hyper operators.

@erik-ic3tp

6 жыл бұрын

Platanov, Yeah, I want to know what's beyond exponentiation. And what the uses are for such operations.

@Platanov

6 жыл бұрын

The only 'practical' use I've ever heard of is using them for representing extremely huge numbers (like Graham's Number), which is kind of a boring use.

@erik-ic3tp

6 жыл бұрын

Platanov, Tetration is very compact. But isn't it used for other purposes (like huge Prime numbers)? That's pretty sad.

@whatno5090

6 жыл бұрын

The Transfinite Hyperoperation is pretty cool too, Pepsi.

You defined at the beginning, that a graph is robber-win, when the robber can hide from the cop for an infinite amount of moves. Doesn't that make the infinte tree graph(6:25) robber-win?

@carsonwood1513

6 жыл бұрын

Vector , no because every branch has a finite amount of points, there are just an infinite number of them.

@RedTriangle53

6 жыл бұрын

all the branches are finite, but there is a limitless number of them.

@dliessmgg

6 жыл бұрын

The infinite tree graph has one branch for every natural number. There is an infinite amount of natural numbers, but none of them is infinitely large. So, the infinite tree graph has an infinite number of branches, but none of them is infinitely long. That means the robber will get to the end of a branch in a finite number of steps, and the cop can trap him there.

@Harryjackgross

6 жыл бұрын

No because he has to pick one to start on, say he choose the Nth one, then the cop will catch him in N+1 moves. Even through there are an infinite number of branches, any individual branch you choose has some finite length.

@JeffQue

6 жыл бұрын

When things goes to omega, cops gets the robber

3, I believe, on any planar graph.

@desertbutterflypic

6 жыл бұрын

2:44

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.

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