BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability Seminar
SUMMARY:Bounding the cop-number of a graph in terms of its
genus - Florian Lehner (University of Warwick)
DTSTART:20180130T150000Z
DTEND:20180130T160000Z
UID:TALK3043AT
URL:/talk/index/3043
DESCRIPTION:The cop-and-robber game is a game on a graph playe
d between two players\, a set of cops\, and a sing
le robber. The rules of the game are as follows: I
n the first round both the cops and the robber cho
ose starting vertices\, in each consecutive even r
ound each cop can move to a neighbouring vertex\,
in odd rounds\, the robber can move to a neighbour
ing vertex. The game has perfect information\, mea
ning that each player knows the positions of both
the cops and the robber at any point in time. The
cops win\, if after some finite number of steps on
e of them occupies the same vertex as the robber\,
otherwise the robber wins. \n\nA graph $G$ is cal
led $k$-cop win\, if for a set of $k$ cops there i
s a strategy to win the game no matter how the rob
ber plays. The cop number $c(G)$ is the least numb
er $k$ such that $G$ is $k$-cop win. This notion w
as first introduced in 1984 by Aigner and Fromme\,
who showed that the cop number of a planar graph
is at most $3$. Using similar techniques\, Quillio
t showed that if $G$ can be embedded on an orienta
ble surface of genus $g$\, then $c(G) \\leq 2g+3$.
Schroeder subsequently improved this bound to $\\
frac 32g+3$ and conjectured an upper bound of $g+3
$.\n\nUsing a reduction to a topological game play
ed on an orientable surface\, we are able to furth
er improve the bound to $\\frac 43 g + 3$ which to
our knowledge is the first improvement since Schr
oeder first formulated his conjecture in 2001. \n(
joint work with N. Bowler\, J. Erde\, and M. Pitz)
\n
LOCATION:Watson LTA
CONTACT:Allan Lo
END:VEVENT
END:VCALENDAR