Seminár z teórie grafov - Ján Pastorek (23.10.2025)
vo štvrtok 23.10.2025 o 9:50 hod. v miestnosti M 213
Prednášajúci: Ján Pastorek
Názov prednášky: Maximal Asymmetric Depth and Conference Graphs
Termín: 23.10.2025, 9:50 hod., M 213
Abstrakt:
Almost all graphs are asymmetric, possessing no nontrivial global automorphisms. Despite this fact, all graphs contain non-trivial local symmetries which we study using isomorphisms between induced subgraphs, known as partial automorphisms. We investigate the extent of asymmetry of graphs through the measure of asymmetric depth defined through the rank of the largest non-trivial partial automorphism. We will show a lower bound for the asymmetric depth of any simple graph Γ on n vertices. Any graph achieving this bound must be a strongly regular graph with parameters (n, (n−1)/2, (n−5)/4, (n−1)/4), also known as a conference graph. We implemented a parallel algorithm 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. We showed that it is of the smallest possible order to attain this bound by checking all asymmetric conference graphs up to 37 vertices.
The talk is based on joint work with Tatiana Jajcayová.