The maximal dimensions of path and graph algebras
prof. dr hab. Piotr M. Hajac, IMPAN, Warszawa
2026-10-28 godz. 13:15 - 14:15
Graph theory is one of the most accessible parts of combinatorics, and one often uses graphs to visualize and study abstract objects in a plethora of mathematical contexts ranging from algebra and functional analysis to K-theory. Better still, the ubiquity of graphs goes beyond mathematics, e.g., Dijkstra’s graph-search algorithm is used in Google Maps. This talk will commence with an abridged hitchhiker's guide to the galaxy of applications of directed graphs. Then we will focus on solving a concrete optimization problem concerning the maximal dimension of both the path algebra and the graph algebra of a connected acyclic directed graph with N edges. The former is a broadly studied universal object, like the tensor algebra, and the latter is simply a matrix algebra. Finally, we will pose some reverse optimization problems: Given a dimension, what is the minimal sufficient number of edges? In particular, we will discuss the optimization-gap problem for matrix algebras, and speculate on its relation with the Cunningham chains of the first kind of prime numbers. (Based on joint work with Ł. Kaczmarczyk, M. Lowiel, and E. A. Pacheco.)
English
Polski
Print
