Scaffolds and quantum isomorphism of graphs
No Thumbnail Available
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
none
Quantum isomorphism, which is originated from solving problems in physics, has now become a crucial concept in graph theory for analyzing the structure of two graphs. It is of great importance to determine whether any given pair of graphs is quantum isomorphic, as well as to identify cases where two graphs are not isomorphic but exhibit quantum isomorphism. Furthermore, it has been observed that graphs are quantum isomorphic only when they contain at least 16 vertices. Thus, the primary objective of this thesis is to address the quantum isomorphism of specific problems and graphs with 16 vertices that are classified based on their girth.The main tool we use in the thesis are two notions called scaffolds and pattern reduction. The former notion is closely associated with counting graph homomorphisms that are relevant to quantum isomorphism, while the latter represents a novel process outlined in this thesis, aiming at simplifying the research procedure. Based on our investigations, we have obtained several results. Firstly, the strongly regular graphs(SRG), specifically the H(2, 4) and the Shrikhande graph, are not quantum isomorphic, and neither are the T(8) and the three Chang graphs. Moreover, when considering two graphs with 16 vertices and respective girths g_1 and g_2, we establish that they are not quantum isomorphic if any of the following conditions hold: (a) both g_1 = g_2 ≥ 9 or ∞; (b) g_1 = g_2 = 8 and both of the graphs are planar or nonplanar. Importantly, through our methods, we are able to generalize part of the results to encompass all graphs. We have concluded that two graphs are not quantum isomorphic under the following conditions: (a) g_1 ≠ g_2 and g = min{g_1, g_2} is odd, or (b) both two graphs are planar, regardless of the number of vertices.
Quantum isomorphism, which is originated from solving problems in physics, has now become a crucial concept in graph theory for analyzing the structure of two graphs. It is of great importance to determine whether any given pair of graphs is quantum isomorphic, as well as to identify cases where two graphs are not isomorphic but exhibit quantum isomorphism. Furthermore, it has been observed that graphs are quantum isomorphic only when they contain at least 16 vertices. Thus, the primary objective of this thesis is to address the quantum isomorphism of specific problems and graphs with 16 vertices that are classified based on their girth.The main tool we use in the thesis are two notions called scaffolds and pattern reduction. The former notion is closely associated with counting graph homomorphisms that are relevant to quantum isomorphism, while the latter represents a novel process outlined in this thesis, aiming at simplifying the research procedure. Based on our investigations, we have obtained several results. Firstly, the strongly regular graphs(SRG), specifically the H(2, 4) and the Shrikhande graph, are not quantum isomorphic, and neither are the T(8) and the three Chang graphs. Moreover, when considering two graphs with 16 vertices and respective girths g_1 and g_2, we establish that they are not quantum isomorphic if any of the following conditions hold: (a) both g_1 = g_2 ≥ 9 or ∞; (b) g_1 = g_2 = 8 and both of the graphs are planar or nonplanar. Importantly, through our methods, we are able to generalize part of the results to encompass all graphs. We have concluded that two graphs are not quantum isomorphic under the following conditions: (a) g_1 ≠ g_2 and g = min{g_1, g_2} is odd, or (b) both two graphs are planar, regardless of the number of vertices.
Description
Keywords
none, SRG, scaffolds, graph homomorphism, quantum isomorphism