Christian Deppe: Combinatorial Two-Sided Search
Deppe ChristianCombinatorial Search Seminar
on 3/29/21
We wish to locate an intruder who is hiding at one of the
vertices of a graph
arbitrary set of
those vertices, then we win. Otherwise, the intruder may choose to move
to an adjacent vertex or remain in place. The intruder is ‘invisible’:
we have no way of knowing if or where the intruder moves. We call the
smallest
after finitely many steps the search number of
describe some results and problems around the search number, with a
particular emphasis on its behavior under edge-subdivisions. This is a
joint work with Anton Bernshteyn (Georgia Tech).