Jak z grafu skierowanego przejść do algebry macierzy? I co wspólnego z takim problemem mogą mieć liczby pierwsze oraz tzw. łańcuchy Cunninghama?

Podczas najbliższego Seminarium Wydziałowego prof. Piotr Hajac (IMPAN) przedstawi problem maksymalizacji wymiaru algebr związanych z grafami acyklicznymi. Wykład pokaże związki między teorią grafów, algebrą i teorią liczb, a w jego końcowej części pojawi się również pytanie o możliwy związek problemu optymalizacyjnego z łańcuchami Cunninghama liczb pierwszych.

Abstrakt

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