Adjacency-degree algebras and spectral determination of graphs

arXiv:2607.21494 · math.CO, math.SP · Submitted 2026-07-23 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Adjacency-degree algebras and spectral determination of graphs".

Emmy: Here's the gist of the paper. The paper proves that principal adjacency-degree moments determine every tree by establishing a linear-algebraic implementation of McKay's leaf-stripping method within a principal cyclic module.

Ada: This result is significant because it provides a sharper spectral determination of trees than previously known methods.

Emmy: Algebraic Framework and Observability The adjacency-degree algebra is defined as (G) = ⟨I, AG, DG⟩ for a finite simple graph G.

Ada: The principal module is then defined as M G = (G)1 be the cyclic module generated by the all-ones vector.

Title and authors: Ada: So we're looking at this paper today, "Adjacency-degree algebras and spectral determination of graphs." It’s talking about how we can use these adjacency and degree measurements to figure out the exact shape of a tree.

Emmy: Exactly. The authors are building this framework around an algebra called the adjacency-degree algebra, which is just the set containing the identity matrix, the adjacency matrix of a graph, and its degree matrix. They call this structure M G when they generate it by taking powers of those three things starting from a vector of all ones.

Kolya: I’m interested in what that actually means for us in terms of computation, Ada. Is this just more abstract algebra, or does it give us something practical?

Ada: Well, the paper shows that they can use a linear-algebraic method to do what McKay did before, which is leaf stripping. They prove this using a principal cyclic module and show that for connected graphs, the ideal in this algebra acts like the full endomorphism algebra on the module generated by all ones.

Emmy: That's key because it links the algebraic structure directly to graph theory. They then use modules like W G, which is called the stable color-refinement module, and U G, which is the automorphism-orbit module, to measure how much information we’re capturing about the graph structure.

Ada: And they establish that a graph is observable if those two modules are equal, meaning it satisfies both principal color-observability and refinability. That's a structural condition they use to filter out graphs that aren't well-behaved in this way.

Kolya: So, if we look at the method itself, what’s the concrete process they are using to get these tree shapes? Is it just some kind of matrix multiplication?

Emmy: They describe a four-step matrix form of McKay's leaf stripping scheme. It involves converting selected leaf sets into diagonal count operators, then using those operators to build idempotents for lower rooted types, and then center selectors produce the seed orbit indicators at the terminal core.

Ada: And finally, they reverse that whole pruning process by moving those indicators back through the steps. That’s how they extract the necessary information from just these principal adjacency-degree moments.

Kolya: Okay, so we've got this method for extracting data from the algebra. But what’s a big result here? What’s the main payoff for someone who only cares about reconstructing a tree?

Emmy: The main result is that for connected trees, the orbit quotient of that tree, which they call Q T, turns out to be the full matrix algebra M m R. That means every possible matrix unit belongs to this quotient structure.

Title and authors: Ada: That’s a strong statement. It tells us that the algebraic structure derived from these moments is rich enough to represent any possible tree geometry in a complete way, up to some relabeling of nodes.

Kolya: Does that mean we can actually use these moments as a sort of fingerprint for trees? What are the limitations they mention?

Emmy: They link principal AD-rigidity to homomorphism counts from degree-decorated caterpillars. This means the moment structure is precisely what you get when you count how many ways you can map a decorated caterpillar onto your graph.

Ada: That’s interesting because it ties spectral data, which is usually about eigenvalues, to counting problems in combinatorics. The paper says the first obstruction to this principal AD-rigidity is an integral switching invisible to the principal module.

Kolya: An integral switching invisible to the principal module sounds like a subtlety we don't see with standard adjacency matrices. What does that actually mean for distinguishing between two graphs?

Emmy: It means there exists a non-zero symmetric integral zero diagonal matrix, let's call it E, such that when you add it to the adjacency matrix of a simple graph G, you get another adjacency matrix A plus E, but this new matrix still has the same principal moments as G.

Ada: So if we only look at those specific moments derived from multiplication in the algebra generated by the adjacency and degree matrices, we might miss these finer distinctions between graphs.

Kolya: That’s a big caveat for anyone trying to use these moments for graph isomorphism testing. It suggests that principal moments are not a complete fingerprint on their own.

Ada: And they show how to fix that by looking at more specific words in the algebra generated by x and y, which they call degree-decorated caterpillar counts. They find that certain finite matrices derived from these counts can determine the weighted orbit quotient of a tree up to relabeling.

Emmy: And this leads to a linear-time algorithm for extracting everything. They construct an AD expression that records the graph-dependent AD expressions whose evaluations are the orbit indicators of the tree.

Kolya: Linear time is great for computation, but what does that algorithm actually give us in terms of output? Is it just a number, or something more structural?

Ada: It gives you the automorphism-orbit partition and the weighted orbit quotient, which they call s i and b i j. Then, they use Theorem five point one to give you a canonical tree code by pruning that quotient from the leaves toward the center.

Emmy: That canonical code is what makes it useful for reconstruction. It’s a way to turn those algebraic invariants back into an actual graph structure efficiently for connected trees, which they prove is determined by these moments.

Title and authors: Kolya: So, if you take any tree and run this algorithm, you get a canonical representation in time that scales linearly with the number of edges. That’s a very concrete result for practical applications.

Ada: It does scale linearly because each edge and vertex is processed only a bounded number of times during the construction process. But we have to remember that this algorithm relies on having those AD expressions available to record.

Emmy: And they do provide finite certificates for specific, tricky cases, like the ten-vertex switch in Example two point two, which you can check directly in Appendix A without needing a massive search.

Kolya: That certificate sounds useful for verification purposes. It’s a compact way to confirm that two graphs are not isomorphic even if their principal moments match.

Ada: Right, and they show that the common Wang pencil polynomial for these two specific non-isomorphic trees is a complex expression involving lambda and t, which is just a slice of the adjacency-degree calculus.

Emmy: That pencil isn't enough on its own though. The main moment theorem uses more than just this one-parameter slice because it considers all words w in the algebra generated by x and y.

Kolya: So, if I had to summarize this for someone who just wants the gist, I’d say these principal moments are a powerful way to determine trees, provided you have access to the right algebraic machinery and you account for those invisible integral switches.

Ada: That’s a good summary. The paper proves that principal AD moments determine every tree by establishing this linear-algebraic implementation of McKay's leaf stripping method within a principal cyclic module.

Emmy: And the real significance is that it provides a sharper spectral determination of trees than what was previously known with other methods, because these moments are tied to degree-decorated caterpillar counts.

Kolya: It sounds like this paper gives us a more robust tool for when we have spectral data that you think should determine a graph structure.

Ada: Precisely. It’s about using the algebra generated by the adjacency and degree matrices to get a sharper picture of tree geometry, and it shows how to do it in linear time.

Emmy: So we’ve seen how they built the framework, what the main results are, and what's left open with those integral switches.

Kolya: I think we need more work on those structural obstructions—the integral switch invisible to the principal module—to fully characterize what makes a graph truly rigid based on these moments.

Ada: Agreed. The paper gives us a very good starting point for understanding this connection between spectral theory and structural graph properties, and it opens up new ways to look at tree reconstruction using these algebraic tools.

The paper's summary: Ada: So, to wrap up this part of the show, we’ve seen how they use these adjacency and degree measurements to figure out tree shapes in a linear time way, and they found that this method gives us a sharper spectral determination than before by linking those moments to counting patterns in caterpillars.

Emmy: Exactly. Think of it like taking data from a graph—just the connections and the degrees—and instead of just looking at the eigenvalues, you're using a whole algebraic machine, this adjacency-degree algebra, to probe deeper into the structure itself. They show that if these moments match for every possible word in their system, then two trees are isomorphic.

Kolya: That sounds powerful because it means we aren't just getting a rough idea of a tree; we’re getting an actual structural determination based on these counts from caterpillars. What about the limitations? What stops this method from being perfect?

Ada: Well, they pointed out that there’s this thing called an integral switching invisible to the principal module. This is a zero diagonal matrix that doesn't change the principal moments of a graph, so if you only look at those specific moments, you might miss that difference between two non-isomorphic graphs.

Emmy: That means for total rigidity, we need to check for these switches too. The real work then becomes finding those structural obstructions—the specific ways a graph can have this switch without changing its principal moments—to really understand the boundary of what these moments can tell us.

Kolya: So it’s not just about the main moment calculation; it’s about looking at the whole structure around that calculation, including these subtle switches. That makes sense for a probabilistic approach too, because those switches are where you'd expect some noise or hidden complexity to pop up.

Ada: Right. And they give us a constructive way to find these things—a linear time algorithm that records the necessary expressions, and finite certificates for specific tricky cases like the ten-vertex switch. It gives us a concrete tool, not just a theoretical possibility.

Emmy: That’s the real utility there; it moves this from abstract theory into something you can actually run on a computer to verify structural properties of graphs efficiently. We’ve got the machinery for reconstruction and verification now, but characterizing exactly what those invisible switches mean for classification is still the next big challenge.

The paper's improvements: Tom: So, we’ve covered how these principal moments help us reconstruct trees in linear time and how they link to caterpillar counts, and now we’re looking at where these authors suggest things could get even better.

Ada: They suggest that the real power comes from using more specific words in the algebra generated by x and y, like those degree-decorated caterpillar counts you mentioned earlier. This lets them move beyond just the basic principal moments to get a much richer set of data points for reconstruction.

Emmy: I agree. It’s like they're saying that just looking at one type of spectral measurement isn't enough; you need to sample the algebra with different combinations of variables to capture the whole geometric picture of the tree. The structure behind it is that these different words generate more specific constraints on the graph’s geometry.

Kolya: So, if they use these more complex words, what does that mean for our probabilistic interpretation? Are we getting better bounds on how accurately we can reconstruct a tree from noisy data?

Ada: They are aiming for a sharper determination. By using these richer words, the functional mu determines the weighted orbit quotient up to an isometry carrying one to one and intertwining those two generators. This means the resulting quotient is even more precise, not just up to relabeling, but with specific geometric constraints.

Emmy: That precision is what makes it useful for testing isomorphism. It suggests that you can use these different words as a kind of filter; if you find that trees don't share the same counts for those specific word combinations, they aren't isomorphic.

Kolya: And those specific word combinations are graph dependent, right? That means the data we collect has to be tailored to the tree structure itself. Does that make it more or less useful when we’re trying to apply this to a large number of graphs?

Ada: It makes it more specific, Kolya. The paper shows that you can choose these words using a greedy approach based on the adjacency degree Krylov basis construction, and you only need at most m accepted words to get the necessary information. That keeps the complexity controlled.

Emmy: So they’re providing a method for selecting the most informative algebraic measurements without having to check every single possible combination of variables in that algebra. It’s about finding the minimal set of measurements that still captures enough structural information to distinguish non-isomorphic trees, which is what we need for classification.

Conclusion: Ada: So, to conclude on "Adjacency-degree algebras and spectral determination of graphs," we’ve seen how using these principal moments, which are linked to caterpillar counts, allows us to reconstruct trees in linear time and gives us a sharper way to tell if two trees are the same structure.

Emmy: Right. The big picture here is that we’re finding a way to use purely algebraic measurements of adjacency and degree matrices—the adjacency-degree algebra—to solve hard combinatorial problems about graph structure, like determining isomorphism.

Kolya: I still wonder about those invisible integral switches, though. If we can't fully characterize what those are, we can't say for sure when a moment calculation is truly complete. What kind of bounds do you have on how often these switches appear in a graph of size n?

Ada: The paper provides finite certificates for specific cases like the ten-vertex switch, which means we can verify those tricky structural issues directly without needing to search through an infinite set of possibilities. But the general problem is characterizing all possible switches that affect only the principal moments.

Emmy: It’s a classification problem in itself, finding what makes a graph rigid based on these moments alone, and that’s where the next step lies—understanding those obstructions more deeply.

Kolya: For me, it's interesting because if we can find a structural reason why these switches only happen under certain conditions—maybe related to some underlying probabilistic property of the tree—then we might be able to use that knowledge to create better estimation bounds for things like queueing networks.

Ada: Exactly. We’re moving from just getting a linear time algorithm for reconstruction, which is great, toward understanding the fundamental algebraic reason why those trees are determined in the first place.

Emmy: So we’ve shown that these principal moments give us a way to probe tree geometry with more precision than standard spectral analysis allows, and now we have tools to verify results and identify where the method needs refinement.

Kolya: It sounds like this work opens up new avenues for using algebraic invariants in areas like network modeling, where you need fast, reliable ways to compare different system configurations.

Ada: Exactly. We’ve established that principal AD moments determine trees by providing a linear-algebraic implementation of McKay's leaf stripping method within the principal cyclic module. That’s the main result for this paper.

Emmy: It provides a sharper spectral determination than previously known methods by tying those moments directly to degree-decorated caterpillar counts.

Kolya: I think it's a solid step forward, especially with that linear time algorithm and the finite certificates for verification. We’re definitely looking into how these algebraic tools can help us handle more complex structures in the next paper we look at.

Shenzhen MSU–BIT University · Guangdong Laboratory of Machine Perception and Intelligent Computing · Beijing Institute of Technology

math.CO, math.SP

Submitted: 2026-07-23

Updated: 2026-11-05

Comments: The main results are reformulated from v1 and results on cographs are added

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: The paper proves that principal adjacency-degree moments determine every tree by establishing a linear-algebraic implementation of McKay's leaf-stripping method within a principal cyclic module.

Key concepts

Adjacency-degree algebra
This is an algebraic structure defined for a simple graph G using the adjacency matrix (AG) and degree matrix (DG). It forms the basis for studying graph properties through its module M_G, which represents the cyclic structure generated by all ones.
Principal AD-Rigidity
This refers to graphs whose principal equivalence class contains only one non-isomorphic graph. This rigidity is determined by monomial principal moments, which correspond to counting homomorphisms from degree-decorated caterpillars. It implies that color refinement equivalence is equivalent to principal equivalence.
Principal-Invisible Integral Switching
This is a specific type of matrix (a nonzero symmetric integral zero-diagonal matrix E) that does not change the principal moments of a graph. This allows for finer distinctions between graphs, as it identifies structural differences invisible to the primary AD module analysis.

Terminology

Summary

The paper proves that principal adjacency-degree moments determine every tree by establishing a linear-algebraic implementation of McKay's leaf-stripping method within a principal cyclic module. This result is significant because it provides a sharper spectral determination of trees than previously known methods. p. 0

Algebraic Framework and Observability

The adjacency-degree algebra is defined as (G) = ⟨I, AG, DG⟩ for a finite simple graph G. The principal module is then defined as M G = (G)1 be the cyclic module generated by the all-ones vector. p. 1 For connected graphs, the ideal (G)J(G), where J = 11T, acts on M G as the full endomorphism algebra. p. 1 The graph-theoretic content is measured by modules like W G and U G, where W G is the stable color-refinement module and U G is the automorphism-orbit module. p. 2 A graph is AD-observable if M G = U G, which requires both principal color-observability and refinability. p. 3

Matrix Form of Leaf Stripping

The proof utilizes a matrix form of McKay's leaf-stripping scheme where pruning data are produced inside the principal adjacency-degree module. This involves four steps:

  1. The leaf diagonal identity converts selected leaf sets into diagonal count operators. p. 4

  2. Guarded pruning uses these diagonal count operators to construct idempotents for lower rooted types. p. 4

  3. Center selectors produce the seed orbit indicators at the terminal core. p. 4

  4. Reverse propagation moves these indicators back through the pruning process. p. 4

Tree Quotient Full-Matrix Rigidity

For connected trees T, the orbit quotient Q T = ⟨I m, B T, Δ T⟩ is shown to be the full matrix algebra M m(R). This is achieved by showing that every coordinate idempotent E i belongs to Q T. p. 8 The proof relies on Lemma 3. p. 83, which states that for every forest F, (F)1 = U F. p. 1

Principal AD-Rigidity and Color Refinement

The principal AD-rigid graphs are those whose principal equivalence class contains no non-isomorphic graph. The monomial principal AD moments correspond precisely to homomorphism counts from degree-decorated caterpillars. p. 2 This implies that color refinement equivalence implies principal equivalence because the latter is equivalent under all tree homomorphism counts. p. 2 The first obstruction to principal AD-rigidity is an integral switching invisible to the principal module. p. 3 p. 3 p. 3

Tree Reconstruction from Moments

The functional mu G(w) = 1 T w(AG, DG)1 determines the pointed finite-dimensional cyclic representation (M G, AGM G, DGM G, 1,) up to an isometry carrying 1 to 1 and intertwining the two represented generators. By Lemma 5. p. 43, this representation determines the weighted orbit quotient of T up to relabeling. p. 7 Finally, Theorem 5. p. 34 concludes that if moments are equal for every word w in R⟨x, y⟩, then T is isomorphic to T'.

Finite Certificates and Algorithmic Extraction

The paper provides a constructive proof yielding a linear-time algorithm which computes the automorphism-orbit partition and the weighted orbit quotient for any tree. This process records graph-dependent AD expressions whose evaluations are the orbit indicators of T. p. 2 The construction in Section 6 allows for the extraction of a canonical tree code and weighted quotient entries b ij. p. 9 This provides a linear-algebraic certificate for the same canonical quotient data. p. 1 The explicit ten-vertex witness in Example 2. p. 1 p. 1 p. 1 p. 1 p. 1 p. 1 p. 12 is certified directly in Appendix A. p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4

Common Wang Pencil Polynomial

For the two non-isomorphic trees displayed in Section 5, the common polynomial is given as a complex expression involving lambda and t. This polynomial is a natural slice of the adjacency-degree calculus. p. 2 p. 2 The principal moment theorem uses more than this one-parameter pencil because it considers all words w in R⟨x, y⟩. p. 2

Finite Graph-Dependent Witnesses

There exist words w i ∈ R⟨x, y⟩ such that the finite matrices (mu T(w rev i wj)), (mu T(w rev i x wj)), and (mu T(w rev i y wj)) determine the weighted orbit quotient of T. These words may be chosen by the greedy AD-Krylov basis construction and are therefore graph-dependent. The deterministic shortlex greedy procedure gives such a basis using at most m accepted words. p. 4

Decorated-Caterpillar Translation

The monomial principal AD moments are precisely homomorphism counts from degree-decorated caterpillars. This is proven by expanding the matrix coefficient and summing over all spine walks to prove the identity. p. 1 This identifies the pattern class behind principal AD-rigidity. p. 1 p. 1 The first obstruction to principal AD-rigidity is an integral switching invisible to the principal module.

Principal-Invisible Integral Switching

A principal-invisible integral switching is a nonzero symmetric integral zero-diagonal matrix E such that EM G = 0 and A + E is again the adjacency matrix of a simple graph. This switch preserves principal moments because if H has adjacency matrix AH = AG + E, then AG agrees with AH on M G, so all principal moments are equal. p. 4 The graph G10 of Example 2. p. 22 is color-refinement-discrete but hence amenable, but G10 ≡prin H10 and G10 ≠ H10. p. 1

Finite Certificates for the Ten-Vertex Switch

A compact, checkable certificate for Example 2.2 is recorded in Appendix A. p. 4 This certificate involves checking displayed closure identities for M G10, repeated principal profiles used by the switch, color-refinement refinement sequence, and the final triangle-count separation. p. 3 The structure of these certificates is highly regular. p. 3 p. 3 p. 3 p. 3

Algorithmic Extraction for Trees

There is a linear-time algorithm which computes its automorphism-orbit partition, its weighted orbit quotient (s i, b ij) and a canonical tree code. The construction in Subsections 3. p. 1 p. 12, 3.3, and 3.4 records the same steps as AD expressions. p. 4 p. 4 Once the orbit indicators are obtained, a single scan of the edges gives the weighted quotient entries b ij and the cell sizes s i. p. 9 p. 9 Theorem 5.1 then gives a canonical code by pruning the weighted orbit quotient from the leaves toward the center. p. 9 p. 9 The process is linear because each edge and vertex is processed a bounded number of times. p. 9 p. 9

Tree Quotient Geometry

The orbit quotient Q T = ⟨I m, B T, Δ T⟩ for a connected tree T is shown to be the full matrix algebra M m(R). This is proven by showing that every coordinate idempotent E i belongs to Q T. p. 8 The proof uses the guarded pruning formulas of Section 3 to show that all matrices constructed remain in Q T. p. 8 This confirms that every matrix unit belongs to Q T. p. 8

Intrinsic Recovery of the Weighted Quotient

The functional mu G(w) = 1 T w(AG, DG)1 determines the pointed finite-dimensional cyclic representation (M G, AGM G, DGM G, 1,) up to an isometry carrying 1 to 1 and intertwining the two represented generators. This representation determines the weighted orbit quotient of T up to simultaneous relabeling. p. 9 The weighted quotient entries are b ij = q ij/s i. p. 9 This is established by showing that the representation determines s i = P i1 squared and q ij =. p. 2

Principal AD Moments Determine Trees

If moments are equal for every word w in R⟨x, y⟩, then T is isomorphic to T'. This follows because equality of the moment functionals gives an isometric isomorphism of the pointed cyclic representations generated by 1. p. 2 Lemma 5.3 then shows that the two trees have the same weighted orbit quotient up to relabeling. p. 9 By Theorem 5. p. 11, this quotient determines the tree. p. 9 The distinguished A-moments are essential for this determination. p. 0

For every graph G, the homomorphism count hom(C(a0, …, al), G) = 1 T D a0 A D a1 A … A D al 1. This identifies the pattern class behind principal AD-rigidity. Color refinement equivalence implies principal equivalence because color refinement is equivalent under all tree homomorphism counts. p. 2 The first obstruction to principal AD-rigidity is an integral switching invisible to the principal module. The resulting classification problem is to characterize principal AD-rigid graphs intrinsically. p. 3 p. 3

The certificate is independent of the enumeration code and involves checking displayed closure identities for M G10, repeated principal profiles used by the switch, color-refinement refinement sequence, and the final triangle-count separation. The explicit ten-vertex witness in Example 2.2 is certified directly in Appendix A. The structure of these certificates is highly regular. The observed gap from amenability arises from graph-realizable integral switchings in directions left unresolved by the principal cyclic module. p. 3 The resulting classification problem is to characterize principal AD-rigid graphs intrinsically.

For the two non-isomorphic trees displayed in Section 5, the common polynomial is given as a complex expression involving lambda and t. This polynomial is a natural slice of the adjacency-degree calculus. McKay’s coalescence construction already gives families of trees with the same A - tD spectrum for every value of t. p. 1 The principal moment theorem therefore uses more than this one-parameter pencil. p. 3

The certificate is independent of the enumeration code and involves checking displayed closure identities for M G10, repeated principal profiles used by the switch, color-refinement refinement sequence, and the final triangle-count separation. The explicit ten-vertex witness in Example 2.2 is certified directly in Appendix A. The structure of these certificates is highly regular. All finite enumerations reported here were carried out with exact integer or rational arithmetic. p. 3 p. 3 The explicit ten-vertex witness in Example 2.2 is certified directly in Appendix A. The complete enumeration records an isomorphic representative of the first graph as I? p. 3 p. 3qbDrs소. The explicit ten-vertex witness in Example 2.2 is certified directly in Appendix A.

There is a linear-time algorithm which computes its automorphism-orbit partition and the weighted orbit quotient (s i, b ij) and a canonical tree code. The construction in Subsections 3.2, 3.3, and 3.4 records the same steps as AD expressions. Once the orbit indicators are obtained, a single scan of the edges gives the weighted quotient entries b ij and the cell sizes s i. Theorem 5.1 then gives a canonical code by pruning the weighted orbit quotient from the leaves toward the center. The process is linear because each edge and vertex is processed a bounded number of times.

The certificate is independent of the enumeration code and involves checking displayed closure identities for M G10, repeated principal profiles used by the switch, color-refinement refinement sequence, and the final triangle-count separation. The explicit ten-vertex witness in Example 2.2 is certified directly in Appendix A. The structure of these certificates is highly regular. All finite enumerations reported here were carried out with exact integer or rational arithmetic. The explicit ten-vertex witness in Example 2.2 is certified directly in Appendix A. The complete enumeration records an isomorphic representative of the first graph as I?qbDrs소.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Principal moments can be used for tree reconstruction by treating them as degree-decorated caterpillar counts, which allows AI systems to determine graph structures from spectral data that are more powerful than standard adjacency spectra.

  2. The system can perform linear-time tree canonization and compute the automorphism-orbit partition directly from principal AD blocks, providing a canonical code for graphs based on these invariants.

  3. AI can distinguish between non-isomorphic graphs by checking if they share the same principal equivalence class, which is a structural notion determined by the principal cyclic noncommutative AD moment problem.

  4. The system can identify integral switching invisible to the principal module, which are nonzero symmetric integral zero-diagonal matrices that do not affect principal moments, allowing for finer distinctions than standard spectral analysis.

  5. The AI can verify if an amenable graph fails principal AD-rigidity by searching for a graph-realizable switching invisible to the principal cyclic module, guiding researchers toward structural obstructions in graph theory.

Sources

Related papers