[專題演講] Counting Paths in Directed Graphs
Counting Paths in Directed Graphs
Prof. Piotr M. Hajac
Institute of Mathematics of the Polish Academy of Sciences, Warsaw, Poland
Date: 2025/11/25 (Tue)
Venue: S4-625
Time: 14:00
Abstract :
Graph theory is considered one of the oldest and most accessible branches of combinatorics and has numerous natural connections to other areas of mathematics. In particular, directed graphs, or quivers, are fundamental tools in representation theory as well as in noncommutative geometry and topology. In this talk, I will consider the class of directed graphs with N ≥ 1 edges and without loops shorter than k. Using the concept of a labelled graph, I will show how to determine graphs from this class that maximize the number of all paths of length k. To end with, I shall pose a related open problem concerning the maximal dimension of the path algebra of an acyclic graph with N ≥ 1 edges, and compute an upper bound for this dimension. Based on joint work with Oskar Stachowiak.