Eugene Lee (Carnegie Mellon): Catching an invisible intruder on subdivisions of a graph

Description of video

Date: 4/26/21
Speaker :Lee Eugene


    We wish to locate an intruder who is hiding at one of the
    vertices of a graph G. At each step, we are allowed to ‘check’an
    arbitrary set of k vertices. If the intruder is presently at any 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 k such that we can guarantee the capture of the intruder
    after finitely many steps the search number of G. In this talk I will
    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).