Doktorandské kolokvium KAI - Ján Pastorek (8.12.2025)
v pondelok 8.12.2025 o 13:10 hod. v miestnosti I 9
Prednášajúci: Ján Pastorek
Názov: Deeply Asymmetric Structures
Termín: 8.12.2025, 13:10 hod., I/9
Abstrakt:
What are symmetries? Symmetries are typically understood globally: an object is symmetric if it has nontrivial automorphisms—transformations preserving the whole structure. It is well-established that almost all graphs are asymmetric, possessing no "global" symmetries. However, global asymmetry does not imply a lack of structure. Every graph exhibits rich "local" symmetries, which we study using isomorphisms between induced subgraphs, known as partial automorphisms.
How far can graphs be from having global symmetries? We investigate this question through the measure of asymmetric depth of graphs defined through the order of the domain of the largest non-trivial partial automorphism. We will report on our progress from previous years. Earlier, we established a new, tight upper bound for the asymmetric depth of any graph. We proved that any graph achieving this bound must be a strongly regular graph. We implemented a parallel algorithm on high-performing cluster Clara for checking asymmetric depth on a high-performance cluster. Using this algorithm, we identified an asymmetric conference graph on 37 vertices that attains this bound, thereby proving its tightness.
Given that most real-world networks such as brain networks are sparse due to connection costs, we have begun extending this investigation to sparse graphs where we can improve the general upper bound. For planar graphs, we established a tight upper bound by finding duals of asymmetric fullerenes.