Logical aspects of isomorphism of controllable graphs and cospectrality of distance-regularized graphs

Imagine you have a massive library of graphs. In the world of mathematics, a "graph" is just a collection of dots (vertices) connected by lines (edges). Think of these as social networks, road maps, or even molecules.

This paper is about a detective story. The detectives are trying to figure out: "If two graphs look the same in a specific way, are they actually the exact same structure?"

The authors use a very specific set of tools to solve this: Logic (specifically, a type of logic that can count) and Spectra (a mathematical "fingerprint" based on numbers).

Here is the breakdown of their findings, explained with everyday analogies.

The Two Main Characters

The paper focuses on two special types of graphs:

Controllable Graphs: Think of these as "responsive" systems. Imagine a row of dominoes or a network of lights. If you push one specific domino (or switch on one light), the whole system reacts in a unique way that allows you to control the entire state of the system. In math terms, these graphs are "controllable" if their internal structure is so unique that you can't trick them with a simple swap.
Distance-Regularized Graphs: Imagine a city where every neighborhood has a very strict, predictable layout. If you stand at any house, the number of houses exactly 1 block away, 2 blocks away, and 3 blocks away follows a perfect pattern. These graphs are highly organized, like a crystal lattice or a perfectly planned grid.

The Detective's Toolkit

To solve the mystery, the authors use two main tools:

The "Counting Logic" (C2 and C3): Imagine a detective who can ask questions like, "Is there a person here who has exactly 3 friends?" or "Are there at least 5 people who know each other?"
- C2 is a detective with a limited memory: they can only hold two names in their head at once while counting.
- C3 is a slightly smarter detective who can hold three names in their head.
- If two graphs are "C2-equivalent," it means this limited detective cannot tell them apart. If they are "C3-equivalent," the slightly smarter detective can't tell them apart either.
The "Spectral Fingerprint" (Cospectrality): Every graph has a hidden "fingerprint" made of numbers called eigenvalues. If two graphs have the exact same list of these numbers, they are cospectral. It's like two different people having the exact same DNA sequence in a specific test. Usually, having the same fingerprint doesn't mean they are the same person, but for these special graphs, it might!

The Big Discoveries

The paper connects these tools to prove two major things:

1. The "Controllable" Mystery (The C2 Detective)

The Finding: If two controllable graphs are indistinguishable to the C2 detective (the one who can only count with two variables), then they are identical (isomorphic).

The Analogy:
Imagine you have two very complex, responsive machines (controllable graphs). You give them a simple test: "Can you count your immediate neighbors and their neighbors?" (This is what the C2 detective does).

In most graphs, two different machines might pass this simple test and look identical to the detective.
But for these special "controllable" machines, the authors prove that if they pass this simple test, they must be the exact same machine. The "controllable" nature makes them so unique that a simple count reveals their true identity.

2. The "Distance-Regularized" Mystery (The C3 Detective)

The Finding: If two distance-regularized graphs have the same Spectral Fingerprint (they are cospectral), then they are indistinguishable to the C3 detective.

The Analogy:
Imagine two perfectly organized cities (distance-regularized graphs).

Usually, two cities can have the same "DNA fingerprint" (spectrum) but be built differently (one might be a grid, the other a hexagon).
However, the authors prove that for these specifically organized cities, if their DNA fingerprints match, then a detective who can count up to three steps away (C3) will see them as identical.
Essentially, for these highly structured graphs, having the same numbers (spectrum) means they are logically indistinguishable.

Why Does This Matter?

In the past, mathematicians used heavy algebra and complex number-crunching to prove these things. This paper is special because it uses logic (the language of computers and reasoning) to prove the same results.

Unification: It shows that "controllability" and "distance-regularity" are not just algebraic quirks; they have deep logical properties.
Simplicity: It proves that you don't need a super-computer to tell these graphs apart. A simple logical check (counting neighbors) is enough to confirm they are the same.

Summary in One Sentence

For highly structured or responsive graphs, if they look the same to a simple logical observer (who can count a few neighbors) or if they share the same mathematical fingerprint, they are actually the exact same graph.

Here is a detailed technical summary of the paper "Logical aspects of isomorphism of controllable graphs and cospectrality of distance-regularized graphs" by Abiad, Dawar, and Zapata-Fonseca.

1. Problem Statement

The paper addresses the relationship between algebraic/spectral properties of graphs and their logical definability. Specifically, it investigates two distinct classes of graphs where traditional characterizations rely on algebraic or spectral tools:

Controllable Graphs: Graphs where the walk matrix is invertible. The problem is to determine if logical equivalence (specifically using counting logic) implies graph isomorphism for this class.
Distance-Regularized Graphs: A generalization of distance-regular and distance-biregular graphs. The problem is to determine if spectral equivalence (cospectrality) implies logical equivalence for this class.

While most existing results for these classes are algebraic, the authors aim to unify and extend these findings using First-Order Logic (FOL), specifically fragments with counting quantifiers ( $C_k$ ).

2. Methodology

The authors employ tools from finite model theory and algebraic graph theory, bridging the gap between logical equivalence and structural properties.

Logical Framework:
- They utilize the logic $C_k$ , which is the fragment of first-order logic restricted to $k$ variables but allowing counting quantifiers ( $\exists^{\ge i} x$ ).
- $C_2$ -equivalence: Two graphs are $C_2$ -equivalent if they satisfy the same sentences with two variables and counting. By the Immerman-Lander theorem, this is equivalent to having the same iterated degree sequences (or being fractionally isomorphic).
- $C_3$ -equivalence: Two graphs are $C_3$ -equivalent if they satisfy the same sentences with three variables. By the Cai-Fürer-Immerman theorem, this is equivalent to their coherent configurations (computed via the 2-dimensional Weisfeiler-Leman algorithm) being intersection equivalent.
Algebraic Tools:
- Walk Matrices: Used to define controllable graphs ( $W_\Gamma = [1, A1, \dots, A^{n-1}1]$ ).
- Coherent Configurations: Used to analyze the structural symmetry of distance-regularized graphs.
- Spectral Theory: Analysis of eigenvalues and intersection arrays to relate cospectrality to structural parameters.

3. Key Contributions and Results

A. Isomorphism of Controllable Graphs

The authors prove that for the class of controllable graphs, logical equivalence in $C_2$ is sufficient to guarantee isomorphism.

Theorem 3.2: Two controllable graphs $\Gamma$ and $\Delta$ are isomorphic if and only if they are $C_2$ -equivalent.
Proof Logic:
1. $C_2$ -equivalence implies the graphs are fractionally isomorphic (same iterated degree sequence).
2. Fractional isomorphism implies walk-equivalence (same number of walks of any length).
3. For controllable graphs, walk-equivalence implies generalized cospectrality (cospectral with cospectral complements).
4. Generalized cospectrality for controllable graphs implies the existence of a matrix $Q$ such that $QAQ^T = B$ and $Q\mathbf{1} = \mathbf{1}$ .
5. Crucially, the walk-equivalence derived from $C_2$ -equivalence forces this matrix $Q$ to be a permutation matrix, thereby proving isomorphism.
Significance: This extends previous results for strongly regular graphs and distance-regular graphs to the broader class of controllable graphs, showing that the "controllability" property makes the graph rigid enough that $C_2$ -equivalence (a relatively weak logical condition) collapses to full isomorphism.

B. Cospectrality of Distance-Regularized Graphs

The authors prove that for distance-regularized graphs, spectral equivalence is equivalent to logical equivalence in $C_3$ .

Theorem 4.5: Two distance-regularized graphs are cospectral if and only if they are $C_3$ -equivalent.
Proof Logic:
1. Distance-regularized graphs are either distance-regular or distance-biregular (Godsil & Shawe-Taylor).
2. For distance-biregular graphs, the authors show that cospectrality implies the graphs have the same intersection arrays (the parameters defining the graph's local structure).
3. Identical intersection arrays imply that the coherent configurations of the two graphs are intersection equivalent (they have the same intersection numbers $p_{ij}(k)$ ).
4. By the Cai-Fürer-Immerman theorem, intersection equivalent coherent configurations imply $C_3$ -equivalence.
5. The converse ( $C_3$ -equivalence $\implies$ cospectrality) is a known result (Theorem 2.3).
Significance: This generalizes a result by Mančinska, Roberson, and Varvitsiotis (which was limited to distance-regular graphs) to the entire class of distance-regularized graphs. It establishes that for these highly structured graphs, the spectral properties are fully captured by the 3-variable counting logic.

4. Significance and Impact

Unification of Fields: The paper successfully unifies algebraic graph theory (spectra, walk matrices, coherent configurations) with finite model theory (logic definability). It demonstrates that logical tools can provide powerful characterizations for classes of graphs traditionally studied via linear algebra.
Extension of Known Results:
- It extends the $C_2$ -isomorphism result from strongly regular graphs to all controllable graphs.
- It extends the $C_3$ -cospectrality result from distance-regular graphs to distance-biregular and distance-regularized graphs.
Rigidity of Controllable Graphs: The result highlights that controllable graphs are "logically rigid." While most graphs require complex logical formulas to distinguish them, controllable graphs are so structurally constrained that the relatively simple $C_2$ logic is sufficient to distinguish non-isomorphic graphs.
Algorithmic Implications: Since $C_k$ -equivalence can be decided in polynomial time (via the Weisfeiler-Leman algorithm), these results suggest that for these specific graph classes, isomorphism and spectral equivalence can be verified efficiently using logical/combinatorial algorithms rather than expensive spectral computations or isomorphism testing.

Conclusion

The paper establishes that for controllable graphs, $C_2$ -equivalence is a complete invariant for isomorphism, and for distance-regularized graphs, $C_3$ -equivalence is equivalent to cospectrality. These findings provide a deeper logical understanding of the structural rigidity inherent in these graph classes, extending the reach of logical definability in algebraic combinatorics.