Uloženo v:
| Hlavní autor: | |
|---|---|
| Médium: | Recurso digital |
| Jazyk: | angličtina |
| Vydáno: |
Zenodo
2026
|
| Témata: | |
| On-line přístup: | https://doi.org/10.5281/zenodo.19732663 |
| Tagy: |
Přidat tag
Žádné tagy, Buďte první, kdo vytvoří štítek k tomuto záznamu!
|
Obsah:
- <p>We attach a finite‑dimensional operator‑algebraic package to every finite simple graph. For an n-vertex graph G, the orbit of its labeled copies inside the labeled graph space \Omega_n forms a single S_n-orbit. This orbit determines an orbit subspace \HH(G)\subseteq\ell^2(\Omega_n), a normalized orbit state, and a commuting family of restricted coordinate‑edge projections. These projections generate a finite‑dimensional operator system \Scan(G) and a finite‑dimensional commutative C^*-algebra \Alg(G). We prove that the orbit states of unlabeled n-vertex graphs form an orthonormal basis of the invariant orbit‑sum subspace of \ell^2(\Omega_n); that the scanning projections generate a finite‑dimensional diagonal algebra naturally represented on the orbit subspace; that the full marked scanning package \Pack(G)=(\HH(G),\{E_{ij}^G\}) is functorial under graph isomorphism; and that this marked package is a complete invariant of the underlying graph up to relabeling. We also show why the unmarked algebra \Alg(G) alone is too coarse to be complete: as an abstract finite‑dimensional commutative C^*-algebra it remembers only the size of the labeled orbit. Thus the paper delivers a proved operator‑algebraic core for the scanning framework and identifies the rigidity questions that remain open.</p> <p>---</p> <p>Methodological Postscript: Generalized Feature Extraction and Cross‑Disciplinary Mapping — A Summary of the Series </p> <p>This paper is the sixth and final instalment of the “ordered vertex patterns and zero‑one scanning tables” series. Reviewing the structure of the entire series: the first paper introduced the basic concepts of ordered vertex patterns and laid the theoretical foundation for the whole framework. The second paper gave a simple reduction of the graph reconstruction conjecture within this framework, establishing a formal bridge between the conjecture and the language of scanning tables. The third paper developed the zero‑one scanning table in full detail, proving its combinatorial completeness as an invariant and providing the technical core for all subsequent work. The fourth paper introduced symmetric pruning and orbit‑stabiliser techniques, reducing the time complexity of the isomorphism test to pseudopolynomial. The fifth paper further refined these methods and achieved a quasi‑polynomial time bound for the graph isomorphism problem within the scanning framework. The present sixth and final paper shifts the emphasis from algorithmic complexity to methodological unification and cross‑disciplinary mapping. The earlier part of this paper already presented the core operator‑algebraic constructions (the marked scanning package as a complete invariant of graph isomorphism). Yet the more important contribution does not lie in these concrete theorems, but in the deeper methodology hidden behind the entire series. Therefore we supplement the paper with this methodological postscript, in order to systematically articulate that methodology and to declare a fundamental paradigm shift in graph theory.</p> <p>I. From concrete constructions to a universal principle</p> <p>Throughout the previous papers we repeatedly used an operation that is simple in appearance but extremely powerful: given a finite simple graph G, first list all permutations of its vertex set (there are n! of them); for each ordering record a 0/1 vector that indicates the presence or absence of edges — this is the “zero‑one scanning table”. Then collect these vectors into a multiset and prove that this multiset is a complete invariant of G. Going further, treat these vectors as an orthonormal basis of a Hilbert space, define orbit states and coordinate projections, thereby encoding G into a concrete family of operators in a finite‑dimensional commutative C^*-algebra (the marked package), and prove that this marked package is a complete invariant while the abstract algebra stripped of coordinate information loses that property.</p> <p>Although these constructions are concrete and effective, looking back at the whole process reveals a deeper fact: we have been doing something much more general — we defined a feature extraction function for graphs that maps the combinatorial information of a graph into a chosen mathematical structure (first multisets, then Hilbert spaces, then operator algebras), and then endowed the target space with a metric meaning (e.g. inner product, projection, spectral decomposition) so that problems that were difficult to express or compare directly in graph theory become computable, comparable and classifiable in the target space. This three‑step pattern — “extract → endow with metric meaning → map across disciplines” — forms the underlying logic of all concrete work in this series.</p> <p>II. Formal statement of the methodology</p> <p>Now we abstract this methodology from the concrete instances and formulate it as a universal framework.</p> <p>Definition (generalised feature extraction function). Let \mathscr{G} be the class of all finite simple graphs (or a wider graph class) and let X be an arbitrary set (or class). A generalised feature extraction function is a map F : \mathscr{G} \to X, which assigns to each graph G a “feature” — which may be a table, a vector, a matrix, a polynomial, a polynomial ideal, an algebraic structure, a geometric object, or even a topological space or an object in a category. The key point is that F(G) should encode at least some combinatorial information of G in a structural way (i.e., graph homomorphisms, isomorphisms etc. should correspond to appropriate structures on X).</p> <p>Definition (endowing with metric meaning). Suppose that X already carries (or can be equipped with) some mathematical structure that allows us to compare, compute, or measure the elements of X. Common choices include: equality and inclusion in the set‑theoretic sense; distance metrics (e.g. Hausdorff distance, edit distance); inner products and orthogonality (e.g. Hilbert spaces); algebraic operations (e.g. groups, rings, modules, algebras); order relations (e.g. partial orders, lattices); topological or uniform structures; morphisms and commutative diagrams in category theory. When we say “endow the features with a metric meaning”, we mean that we explicitly define a way such that some kind of “distance” or “similarity” between F(G) and F(H) reflects the graph‑theoretic relation between G and H (e.g., isomorphism, homomorphism, subgraph relation). In this series we embedded the scanning‑table vectors into a Hilbert space and took inner products, thereby giving orthogonality to orbit states and achieving complete distinction of graph isomorphism.</p> <p>Definition (cross‑disciplinary mapping). Once we have chosen a feature extraction function F and a metric meaning on the target space X, we have in fact established a mapping from graph theory to another subfield of mathematics (e.g. combinatorics, linear algebra, functional analysis, topology, probability, algebraic geometry, operator algebras, quantum information, etc.). Problems that were difficult in the original graph setting — such as deciding isomorphism, computing the automorphism group, reconstructing subgraphs, finding a maximum clique — can be translated into problems in X, solved there using the well‑developed tools of that field, and then (if possible) interpreted back into graph‑theoretic language.</p> <p>III. Generality and flexibility of the methodology</p> <p>The most striking feature of this methodology is its high degree of generality and flexibility. The feature extraction function F is completely free: it can be based on all vertex orderings (as in this series’ global scanning table), or on local subgraphs (such as k-subgraph counts), or on random sampling, spectral decomposition, the Laplacian, the chromatic polynomial, the clique polynomial, etc. Importantly, F need not be injective — in many situations we do not need to distinguish all graphs, but only to separate a certain class of properties of interest. Hence the researcher can choose the most suitable feature extraction and target space according to the problem at hand.</p> <p>More radically, we may even define a family of feature extraction functions \{F_t\}_{t \in T} where t is a parameter (e.g. the row index in scanning, the number of colours, a temperature parameter), thereby obtaining a feature family. The “scanning table” in this series is essentially a 0/1-sequence recorded row by row according to vertex order. If we treat each row as an independent polynomial coefficient, or each column as a time series, then the resulting “scanning space” can be endowed with even richer structures. For example, we could choose one polynomial for the first row, a different polynomial for the second row, or even map each row/column to a different mathematical object (a matrix, an operator, a group element). As long as the row‑wise/column‑wise rule is well defined and we can endow the target space with an appropriate metric meaning, we obtain a finer and potentially more expressive interdisciplinary bridge.</p> <p>In an extreme scenario, we could even take “the entire set‑theoretic universe” as the target space: assign to each graph G some set at a level of the von Neumann hierarchy, provided the construction is rigorous and consistent. Of course, this is more a philosophical possibility than a practical suggestion. Nevertheless, it illustrates the inclusiveness of the methodology: it does not restrict what mathematical objects one may use, only that the feature extraction function and the metric meaning are clearly specified.</p> <p>IV. Attitude toward the reconstruction conjecture and future prospects</p> <p>During the writing of this series, the author repeatedly pondered one famous open problem in graph theory — the graph reconstruction conjecture (Kelly–Ulam). This methodology naturally suggests a potential approach: if we can define a feature extraction function F such that F(G) is completely determined by the multiset of vertex‑deleted subgraphs \operatorname{Deck}(G), and F is complete (i.e., F(G)=F(H)\iff G\cong H), then the reconstruction conjecture would be equivalent to the existence of such an F. In this series we have already proved that the global scanning table multiset is complete, but it clearly contains more information than just \operatorname{Deck}(G) — it is not determined by the deck. So the question remains: is there a more economical feature that can be recovered from the deck? Alternatively, can we combine the scanning tables with an appropriate metric meaning so that the subgraph information becomes sufficient to infer the whole graph?</p> <p>During the work, the author had some preliminary ideas, for instance using the inductive structure of multi‑layer scanning tables, or using entropy in the trace state space of the C^*-algebra. However, these ideas are not yet mature, and moreover the author has become completely exhausted — the six papers of this series cover a vast territory from combinatorial counting to operator algebras, consuming enormous energy. Therefore the decision has been made to set aside the direct assault on the reconstruction conjecture. We leave this problem to future generations, hoping that young researchers, using the methodology proposed here or by connecting graph theory with other disciplines (e.g., dynamical systems, algebraic geometry, computational complexity theory), will eventually conquer it.</p> <p>V. Declaration of a new era</p> <p>To summarise, the ultimate contribution of this paper is not a specific theorem, but rather a way of thinking about graph theory: we no longer view a graph as an isolated, static structure consisting only of vertices and edges, but as a source object capable of projecting itself into countless mathematical universes. Every choice of a feature extraction function and a metric meaning opens a new path from graph theory to another domain, thereby bringing endless new problems, new methods, new concepts into graph theory, and at the same time supplying other fields with a rich source of structured examples and challenges.</p> <p>Therefore we hereby declare: a new era of graph theory has arrived. In this new era, the task of graph theorists is not only to study the intrinsic properties of graphs, but also to invent and explore cross‑disciplinary bridges that use graphs as a link between different branches of mathematics. Whether the graph reconstruction conjecture will eventually be solved in some other field, and whichever techniques future researchers might employ, they will not be able to avoid the fact that they are, in essence, putting into practice the methodology of “generalised feature extraction and cross‑disciplinary mapping” articulated in this paper. And the present series, despite containing a large number of concrete constructions and proofs, is in its essence merely a footnote to this methodology.</p> <p>We conclude this final paper with fatigue but satisfaction. The road ahead is long, but the direction has been indicated. May future scholars, standing on the shoulders of this work, see farther and broader landscapes.</p>