The Cops and Robbers Theorem | Infinite Series
Viewers like you help make PBS (Thank you 😃) . Support your local PBS Member Station here: https://to.pbs.org/donateinfi
Can a cop catch a robber? There's some surprising and compelling graph theory that go into answering that question.
Tweet at us! @pbsinfinite
Facebook: facebook.com/pbsinfinite series
Email us! pbsinfiniteseries [at] gmail [dot] com
Previous Episode
Higher Dimensional Tic Tac Toe | Infinite Series
https://www.youtube.com/watch?v=FwJZa-helig&t=17s
Cops and Robbers is played on a finite and connected graph - meaning that any two vertices are joined by a path of edges. The game begins by placing a cop and a robber each on a single vertex; we say it “occupies” that vertex. They alternate moving along the edges, from a vertex to neighboring vertex. Or, on any given turn, the player can choose to not move -- to stay where they are. We’ll assume that the cop always goes first. If, eventually, the cop lands on the robber’s vertex, the game is over -- we say that the game is a “win” for the cop. But, if the robber can avoid the cop indefinitely, we say that the game is a win for the robber.
Written and Hosted by Kelsey Houston-Edwards
Produced by Rusty Ward
Graphics by Ray Lux
Assistant Editing and Sound Design by Mike Petrow
Made by Kornhaber Brown (www.kornhaberbrown.com)
Resources:
M. Aigner and M. Fromme -- A Game of Cops and Robbers:
https://www.math.ucdavis.edu/~erikslivken/classes/2016_spring_180/aigner%20fromme.pdf
The Game of Cops and Robbers on Graphs - Anthony Bonato and Richard Nowakowski
Anthony Bonato -- "What is... Cops and Robbers" http://www.ams.org/notices/201208/rtx120801100p.pdf
Brendan W. Sullivan, Nikolas Townsend, Mikayla Werzanski - “An Introduction to Lazy Cops and Robbers on Graphs,” to appear in College Mathematics Journal in 2017
Brendan W. Sullivan, Nikolas Townsend, Mikayla Werzanski "The 3x3 rooks graph is the unique smallest graph with lazy cop number 3" -- https://arxiv.org/abs/1606.08485
Special Thanks to Anthony Bonato and Brendan Sullivan
Thanks to Matthew O'Connor and Yana Chernobilsky who are supporting us on Patreon at the Identity level!
And thanks to Nicholas Rose and Mauricio Pacheco who are supporting us at the Lemma level!
Видео The Cops and Robbers Theorem | Infinite Series канала PBS Infinite Series
Can a cop catch a robber? There's some surprising and compelling graph theory that go into answering that question.
Tweet at us! @pbsinfinite
Facebook: facebook.com/pbsinfinite series
Email us! pbsinfiniteseries [at] gmail [dot] com
Previous Episode
Higher Dimensional Tic Tac Toe | Infinite Series
https://www.youtube.com/watch?v=FwJZa-helig&t=17s
Cops and Robbers is played on a finite and connected graph - meaning that any two vertices are joined by a path of edges. The game begins by placing a cop and a robber each on a single vertex; we say it “occupies” that vertex. They alternate moving along the edges, from a vertex to neighboring vertex. Or, on any given turn, the player can choose to not move -- to stay where they are. We’ll assume that the cop always goes first. If, eventually, the cop lands on the robber’s vertex, the game is over -- we say that the game is a “win” for the cop. But, if the robber can avoid the cop indefinitely, we say that the game is a win for the robber.
Written and Hosted by Kelsey Houston-Edwards
Produced by Rusty Ward
Graphics by Ray Lux
Assistant Editing and Sound Design by Mike Petrow
Made by Kornhaber Brown (www.kornhaberbrown.com)
Resources:
M. Aigner and M. Fromme -- A Game of Cops and Robbers:
https://www.math.ucdavis.edu/~erikslivken/classes/2016_spring_180/aigner%20fromme.pdf
The Game of Cops and Robbers on Graphs - Anthony Bonato and Richard Nowakowski
Anthony Bonato -- "What is... Cops and Robbers" http://www.ams.org/notices/201208/rtx120801100p.pdf
Brendan W. Sullivan, Nikolas Townsend, Mikayla Werzanski - “An Introduction to Lazy Cops and Robbers on Graphs,” to appear in College Mathematics Journal in 2017
Brendan W. Sullivan, Nikolas Townsend, Mikayla Werzanski "The 3x3 rooks graph is the unique smallest graph with lazy cop number 3" -- https://arxiv.org/abs/1606.08485
Special Thanks to Anthony Bonato and Brendan Sullivan
Thanks to Matthew O'Connor and Yana Chernobilsky who are supporting us on Patreon at the Identity level!
And thanks to Nicholas Rose and Mauricio Pacheco who are supporting us at the Lemma level!
Видео The Cops and Robbers Theorem | Infinite Series канала PBS Infinite Series
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
How Many Cops to Catch a Robber? | Infinite SeriesAmazing Graphs III - NumberphileProving Pick's Theorem | Infinite SeriesThe Devil's Staircase | Infinite SeriesHow to Break Cryptography | Infinite SeriesBeyond the Golden Ratio | Infinite SeriesHow to Generate Pseudorandom Numbers | Infinite SeriesSimplicial Complexes - Your Brain as Math Part 2 | Infinite SeriesCrisis in the Foundation of Mathematics | Infinite SeriesThe Mathematics of Diffie-Hellman Key Exchange | Infinite SeriesSingularities Explained | Infinite SeriesThe Heat Equation + Special Announcement! | Infinite SeriesHilbert's 15th Problem: Schubert Calculus | Infinite SeriesWhen Pi is Not 3.14 | Infinite Series | PBS Digital StudiosKill the Mathematical Hydra | Infinite SeriesWhat was Fermat’s “Marvelous" Proof? | Infinite SeriesSolving the Wolverine Problem with Graph Coloring | Infinite SeriesAn Argument Against Reality - Why You Can't Trust Your SensesInstant Insanity Puzzle | Infinite SeriesVoting Systems and the Condorcet Paradox | Infinite Series