School Seminars and Colloquia

Describing lengths of walks in directed graphs

Discrete Structures and Algorithms (Seminar)

by Anthony Widjaja Lin


Institution: Oxford University
Date: Wed 2nd May 2012
Time: 10:00 AM
Location: Room 215, Richard Berry Building

Abstract: Consider an arbitrary directed graph G and fix a source node s and a sink node t. Is there a nice way to describe the set of *lengths* of walks from s to t? This is a subcase of a more general problem from the theory of automata on words (a subarea of computer science) with a simple graph-theoretic formulation. In this talk, we will show that the set of lengths of walks from s to t can be described as a union of a small number of arithmetic progressions (i.e. sets of the form {a+bn : n is a natural number}), each of small size. [More precisely, a union of quadratically many arithmetic progressions with offsets quadratic in the size of G and periods linear in the size of G.] Furthermore, the computation of this set can be done in polynomial time. This original proof of this result, which is called
Chrobak-Martinez Theorem, has a subtle mistake. The talk will describe
the corrected proof of the result.