# 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.