Doktorandské kolokvium KAI - Ján Pastorek (24.3.2025)
v pondelok 24.3.2025 o 13:10 hod. v miestnosti I/9
Prednášajúci: Ján Pastorek
Názov: Graph isomorphism, asymmetric graphs and partial symmetries
Termín: 24.3.2025, 13:10 hod., I/9
Abstrakt:
Graphs, composed of vertices connected by edges, model many complex systems encountered in science and engineering. Although almost all graphs are asymmetric—that is, they admit only the trivial automorphism—some graphs appear intuitively symmetric even though they possess no nontrivial automorphisms. The Graph Isomorphism Problem (GI), which asks whether two graphs are structurally identical, and the Graph Asymmetry Problem (GA), which determines whether a graph is asymmetric, are two prominent unresolved problems in theoretical computer science. Their computational complexity remains open; neither problem is known to belong to class P nor to be NP-complete. Moreover, it is unclear whether GI can be reduced to GA or what the precise relationship between symmetry and asymmetry in graphs might be. In his plenary talk at ICM 2018, Babai suggested that new insights into GI and GA might arise from a deeper understanding of the local structure of graphs. Local structure of graphs can be studied using partial automorphisms—namely, isomorphisms between induced subgraphs. In our work, we define the symmetry level of a graph as the ratio of the largest rank (i.e., the size of the domain) of a nontrivial partial automorphism to the order of the graph. We further refine theoretical bounds on this measure and identify extremal examples through the use of parallel algorithms implemented in Julia.Fotku prikladam do prilohy.