Daniel Wise

McGill University

Counting W-cycles in a labelled digraph

A "W-cycle" in a labelled digraph G is a closed path whose label is the word W. I will describe a simple result about counting the number of W-cycles in a deterministically labelled connected digraph. Namely: the number of W-cycles in G is bounded by |E(G)|-|V(G)|. The result is related to recent developments in combinatorial group theory, and after describing the result I'll give a quick idea of the connection. This is joint work with Joseph Helfer. And proven independently by Louder-Wilton.