תאוריה של רשתות גרפיות עם פרמטרים: רוטינג אנטאנגלמנט, הפשטת רכיבים וטומוגרפיה א-ספציפית

תקציר מקורי באנגליתarXiv:2609.04165v1 Announce Type: cross Abstract: Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In t