簡易檢索 / 詳目顯示

研究生: 林念瑩
Lin, Nien-Ying
論文名稱: Scaffolds and quantum isomorphism of graphs
Scaffolds and quantum isomorphism of graphs
指導教授: 林延輯
Lin, Yen-Chi Roger
口試委員: 林延輯
Lin, Yen-Chi Roger
郭君逸
Guo, Jun-Yi
俞韋亘
Yu, Wei-Hsuan
口試日期: 2023/06/28
學位類別: 碩士
Master
系所名稱: 數學系
Department of Mathematics
論文出版年: 2023
畢業學年度: 111
語文別: 英文
論文頁數: 38
英文關鍵詞: SRG, scaffolds, graph homomorphism, quantum isomorphism
DOI URL: http://doi.org/10.6345/NTNU202300788
論文種類: 學術論文
相關次數: 點閱:108下載:17
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 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.

    1 Introduction  1 2 Association schemes and scaffolds  2 2.1 Association schemes 3 2.2 Scaffolds  4 3 Counting graph homomorphisms by scaffolds    6 3.1 Necessary conditions for quantum isomorphic graphs  7 3.2 Examples of graphs that are not quantum isomorphic   9 3.2.1 Two specific graphs   9 3.2.2 The H(2, 4) and the Shrikhande graph 10 3.2.3 The T(8) and three Chang graphs 12 4 Quantum isomorphism of 16-vertex graphs with large girth  12 4.1 Counting graph homomorphisms    13 4.2 Graphs with different girth  17 4.3 Graphs with the same girth and g ≥ 9 26 4.4 Graphs with the same girth and g = 8 28 5 Discussion   35 References   37

    Albert Atserias, Laura Mančinska, David E Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136:289–328, 2019.
    Norman Biggs, Norman Linstead Biggs, and Biggs Norman. Algebraic graph theory. Number 67. Cambridge University Press, 1993.
    Andries E Brouwer and Willem H Haemers. Distance-regular graphs. Springer, 2012.
    Andries E Brouwer, AM Cohen, and A Neumaier. Distance-regular graphs, Springer-Verlag, Berlin etc. 1989.
    Ada Chan and William J Martin. Quantum isomorphism of graphs from association schemes. arXiv preprint arXiv:2209.04581, 2022.
    Yoshimi Egawa. Characterization of H(n, q) by the parameters. Journal of Combinatorial Theory, Series A, 31(2):108–125, 1981.
    Chris Godsil and Gordon F Royle. Algebraic graph theory, volume 207. Springer Science & Business Media, 2001.
    Casimir Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta Mathematicae, 15(1):271–283, 1930.
    Xiaoye Liang, Ying-Ying Tan, Hajime Tanaka, and Tao Wang. A duality of scaffolds for translation association schemes. Linear Algebra and its Applications, 638:110–124, 2022.
    Laura Mančinska and David E Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 661–672. IEEE, 2020.
    William J Martin. Scaffolds: a graph-theoretic tool for tensor computations related to Bose-Mesner algebras. Linear Algebra and its Applications, 619:50–106, 2021.
    Ion Nechita, Simon Schmidt, and Moritz Weber. Sinkhorn algorithm for quantum permutation groups. Experimental Mathematics, pages 1–13, 2021.
    Simon Schmidt. Quantum automorphism groups of finite graphs. 2020.
    Simon Schmidt. On the quantum symmetry of distance-transitive graphs. Advances in Mathematics, 368:107150, 2020.
    W. A. Stein et al. Sage Mathematics Software (Version 9.3). The Sage Group, 2021. http://www.sagemath.org.
    Paul Terwilliger. A characterization of P-and Q-polynomial association schemes. Journal of Combinatorial Theory, Series A, 45(1):8–26, 1987.
    Stanisław L Woronowicz. Compact matrix pseudogroups. Communications in Mathematical Physics, 111:613–665, 1987.
    Stanisław L Woronowicz. A remark on compact matrix quantum groups. Letters in Mathematical Physics, 21(1):35–39, 1991.

    下載圖示
    QR CODE