Doktorandské kolokvium KAI - Ján Pastorek (13.5.2024)
v pondelok 13.5.2024 o 13:10 hod. v miestnosti I/9
Prednášajúci: Ján Pastorek
Názov: Partial automorphisms and asymmetry level of graphs
Termín: 13.5.2024, 13:10 hod., I/9
Abstrakt:
Graphs consisting of nodes interconnected by links can express underlying structure of many things we encounter. These graphs frequently exhibit "asymmetric" features but also various kinds of "symmetry". What is the relation between "symmetry" and "asymmetry" of graphs?
Understanding the complex relationships among asymmetric graphs, regular graphs, and graphs with non-trivial automorphisms is challenging. The majority of graphs are well-known to be asymmetric, i.e., having no non-trivial automorphisms. Interestingly, almost all regular graphs, where all "highly-symmetric graphs" concentrate, have only trivial automorphisms, with the Frucht graph being one of the smallest. Notably, removing a single vertex from a graphical regular representation, which captures one of the notions of symmetry, can yield an asymmetric graph. On the other hand, there exist minimal asymmetric graphs where each vertex-induced subgraph possesses non-trivial automorphisms. But already any two-vertex induced subgraph in a graph has non-trivial automorphism.
These findings highlight the importance of partial automorphisms, which are isomorphisms between two induced subgraphs of a graph. Our research delves into the properties of the partial automorphisms of graphs, focusing on the measure of (a)symmetry of a graph, defined as the ratio of the largest rank of a non-trivial partial automorphism to the graph's order. In our presentation, we will discuss computational and theoretical insights from our research in this area.