2014/09/11 by Simon Thwaite, Thwaite, Simon
Mathematics · #05C20 #05C38 (Secondary) #05C70 (Primary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C20 #msc:05C38 #msc:05C70
paper · pdf · doi:10.48550/arxiv.1409.3555
55 pages; significantly restructured and expanded from v1
arxiv created 2014/11/17 · arxiv updated 2014/11/18
We present a family of partitions of WG, the set of walks on a directed graph G. Each partition in this family is identified by an integer sequence K, which specifies a collection of cycles on G with a certain well-defined structure. We term such cycles resummable, and a walk that does not traverse any such cycles K-irreducible. For a given value of K, the corresponding partition of WG consists of a collection of cells that each contain a single K-irreducible walk i plus all walks that can be formed from i by attaching one or more resummable cycles to its vertices. We characterise the entire family of partitions of WG by giving explicit expressions for the structure of the K-irreducible walks and the resummable cycles for arbitrary values of K. We demonstrate how these results can be exploited to recast the sum over all walks on a directed graph as a sum over dressed K-irreducible walks, and discuss the applications of this reformulation to matrix computations.