Kiedy: 15 października 2026 (czwartek), godz. 13:15
Gdzie: sala A.1.14, budynek C-19, Politechnika Wrocławska

Temat: The maximal dimensions of path and graph algebras
Prelegent: prof. Piotr Hajac, Instytut Matematyczny Polskiej Akademii Nauk

Na najbliższym Seminarium Wydziałowym prof. Piotr Hajac (IMPAN) opowie o maksymalnych wymiarach algebr związanych z grafami acyklicznymi. Wykład rozpocznie się od krótkiego przeglądu zastosowań grafów skierowanych – od matematyki po algorytmy wykorzystywane w codziennych aplikacjach, takich jak Google Maps – a następnie przejdzie do konkretnego problemu optymalizacyjnego.

Poszukiwane będą m.in. odpowiedzi na pytanie, jak duży może być wymiar algebry ścieżek i algebry grafu przy ustalonej liczbie krawędzi. Na koniec pojawią się również pytania odwrotne: jeśli znamy wymiar algebry, to ile krawędzi wystarczy, aby go osiągnąć? W tym kontekście pojawia się interesujące zagadnienie związane z algebrami macierzowymi oraz hipoteza dotycząca jego możliwego związku z łańcuchami Cunninghama liczb pierwszych.

Spotkanie będzie więc okazją do zobaczenia, jak pozornie prosta struktura, jaką jest graf, prowadzi do pytań łączących kombinatorykę, algebrę i teorię liczb.

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