Which Vertical Graphs are Non VPHT Reconstructible?

This paper investigates the non-injectivity of the verbose persistent homology transform (VPHT) for graphs with collinear vertices, identifying necessary and sufficient conditions for their non-reconstructibility to advance a complete classification of such cases.

The Gist

Imagine you have a mysterious 3D object, like a sculpture made of wire. You want to describe it to a friend who can't see it. One way to do this is to shine a light on it from every possible angle and record the shadows it casts. In the world of math, this "shadow" is called a Persistent Homology Transform (PHT). It's a topological summary that captures the shape's features (like holes, loops, and separate pieces) as you "sweep" a line across it.

Usually, this shadow is so detailed that if you have the shadows from all angles, you can perfectly rebuild the original object. It's like having a complete set of blueprints.

However, this paper asks a tricky question: What if the object is built in a weird, degenerate way? Specifically, what if all the "dots" (vertices) of the object are lined up perfectly on a single straight vertical pole, like beads on a string?

The authors investigate these "Vertical Graphs" to see if their "shadows" (called VPHT) are still unique. They found that sometimes, two completely different wire sculptures can cast the exact same shadows, making them impossible to tell apart.

Here is the breakdown of their discovery using simple analogies:

1. The "Beads on a String" Setup

Imagine a vertical pole. You can stick beads (vertices) on it at different heights. You can also run rubber bands (edges) between these beads.

• Normal Case: If the beads are scattered randomly in space, the shadows are unique. You can always tell the shape apart.
• The Problem Case: If all beads are on one vertical line, the "shadows" become less informative. The authors focus on this specific, simplified scenario.

2. The "Colliding Pair" (The Magic Trick)

The paper discovers a special relationship between two different graphs that makes them look identical. They call this a "Colliding Pair."

Think of it like two different dance routines performed by two groups of people standing in a line:

• Group A (Graph 1): They move in a specific pattern of "up" and "down" steps.
• Group B (Graph 2): They move in a different pattern.
• The Trick: If you combine both groups into one big circle and look at how they move, their steps form a perfect, alternating loop (Up, Down, Up, Down...).

If this "alternating loop" exists, the two groups produce the exact same shadow when viewed from the top or bottom, even though their individual dance moves (edges) are different. To an observer only seeing the shadows, Group A and Group B are indistinguishable.

3. The "Verbose" Detail

The authors use a super-detailed version of the shadow called the Verbose Persistent Homology Transform (VPHT).

• Standard Shadow: Just tells you "a hole appeared."
• Verbose Shadow: Tells you "a hole appeared at this exact second, and it was created by this specific bead."

Usually, this extra detail is enough to solve the mystery. But the authors found that even with this super-detailed info, if the beads are lined up vertically and form these special "Colliding Pairs," the mystery remains unsolved. The shadows are identical down to the last detail.

4. The "Even Number" Rule

How do you know if a graph is part of a "Colliding Pair" without drawing it? The authors found a simple rule:

• Look at any bead on the string.
• Count how many rubber bands connect to beads below it.
• Count how many rubber bands connect to beads above it.
• The Rule: If every single bead has an even number of connections going up and an even number going down, then this graph is likely part of a "Colliding Pair" and cannot be uniquely reconstructed.

It's like a balance scale. If the weight going up and the weight going down are perfectly balanced (even numbers) at every single point, the structure becomes "invisible" to the VPHT.

5. The Computer Check

The authors didn't just guess; they wrote a computer program to test thousands of small graphs (up to 7 beads).

• The Result: Every single time they found two different graphs that looked the same, those graphs followed the "Colliding Pair" rule.
• The Conclusion: This suggests that the "Colliding Pair" is the only reason these vertical graphs become un-reconstructible. If your graph doesn't fit this pattern, you can safely assume its shadow is unique.

Summary

In everyday terms:
If you build a structure where all the joints are stacked in a straight line, you might think you can describe it perfectly by looking at it from the top and bottom. But this paper proves that two completely different structures can look exactly the same if they are built with a specific "alternating" pattern of connections.

It's like two different keys that happen to have the exact same silhouette when held up to a light. Unless you know the secret "even-number" rule, you can't tell them apart just by looking at their shadows. This helps mathematicians understand the limits of topological data analysis and when we need to be careful about assuming a shape is unique based on its data.

Technical Summary

Here is a detailed technical summary of the paper "Which Vertical Graphs are Non VPHT Reconstructible?" by Gutzeit, Kistler, Ophelders, and Schenfisch.

1. Problem Statement

The paper addresses a fundamental question in Topological Data Analysis (TDA): Under what conditions is a shape uniquely determined by its topological summary?

• Context: The Persistent Homology Transform (PHT) and its more discriminative variant, the Verbose Persistent Homology Transform (VPHT), map a shape (specifically simplicial complexes or graphs) to a collection of persistence diagrams corresponding to height filtrations in all possible directions.
• Known Results: It is established that for shapes in "general position" (where no two vertices share the same coordinate in any projection direction), the VPHT is injective, meaning the shape can be perfectly reconstructed from the transform.
• The Gap: The authors investigate the degenerate case where general position is violated. Specifically, they focus on vertical graphs—graphs where all vertices are collinear (aligned on a vertical line). In this setting, the VPHT may fail to be injective, meaning two distinct graphs could produce identical VPHTs.
• Goal: To identify necessary and sufficient conditions for a vertical graph to be non-VPHT-reconstructible (i.e., indistinguishable from another graph via the VPHT).

2. Methodology

The authors employ a hybrid approach combining rigorous theoretical proofs with computational verification.

A. Theoretical Framework

1. Definitions:
   • Vertical Graph: Vertices $v_1, \dots, v_n$ lie on a vertical line with $v_i < v_j$ if $i < j$.
   • VPHT: The set of verbose persistence diagrams for all directions. Due to symmetry, for vertical graphs, the VPHT is fully determined by the diagrams in the up and down directions.
   • Verbose Diagrams: Unlike standard diagrams, these include points on the diagonal representing the instantaneous birth and death of components (corresponding to vertices and edges).
2. Key Observation: There is a bijection between:
   • Vertices and points recording connected component births (birth coordinate = vertex height).
   • Edges and points recording cycle births or component deaths (birth/death coordinates = edge height).
3. Structural Concepts:
   • Colliding Pairs: Two graphs $G_1$ and $G_2$ form a "simple colliding pair" if orienting $G_1$'s edges upward and $G_2$'s edges downward creates an alternating cycle in their disjoint union $G_1 \sqcup G_2$.
   • Type G Graphs: Graphs that can be partitioned into alternating cycles, where each cycle can be further split into a colliding pair.
4. Proof Strategy:
   • The authors analyze the degree constraints of vertices in the disjoint union.
   • They prove that if a graph is of "Type G" (partitionable into alternating cycles with specific degree parity), the verbose diagrams for the constituent subgraphs $G_1$ and $G_2$ are identical in the up/down directions.
   • They utilize Veblen's Theorem regarding Eulerian graphs to establish the relationship between cycle partitioning and vertex degrees.

B. Computational Approach

• Tool Development: The authors created a custom GUI application (vpht-algo) to visualize persistence diagrams and perform brute-force searches.
• Search Space: They exhaustively searched for pairs of vertical graphs with up to 7 vertices that share the same VPHT.
• Constraints: The search was limited to simple graphs with vertices projected onto a line, filtering for "collision sets" (pairs with identical VPHTs).
• Scaling: Due to the combinatorial explosion ($2^{n(n-1)/2}$), computations were feasible up to$n=7$(taking seconds) but became intractable for$n=8$ (hours).

3. Key Contributions and Results

A. Characterization of Non-Reconstructibility

The paper provides a classification of vertical graphs that are not uniquely reconstructible:

1. Theorem 9 (Special Colliding Pairs): If a graph $G$ is of "Type G" (partitionable into alternating cycles) and every vertex has a degree of at most 4 (specifically, no more than two lower and two upper neighbors), then the partitioned subgraphs $G_1$ and $G_2$ are non-VPHT-reconstructible. Their VPHTs are identical.
2. Theorem 11 (Necessity): Conversely, if a pair of vertical graphs $(G_1, G_2)$ is not a colliding pair, their VPHTs are distinct. This establishes that being a colliding pair is a necessary condition for non-reconstructibility in this setting.
3. Lemma 10 (Degree Parity): A vertical graph is of Type G if and only if every vertex has an even number of lower neighbors ($ldeg$) and an even number of upper neighbors ($hdeg$). This parity condition is the algebraic root of the non-reconstructibility.

B. Computational Verification

• Lemma 13: Computational results confirm that for all vertical graphs with up to 7 vertices, any pair sharing the same VPHT is a colliding pair.
• Corollary 15: For these small graphs, the colliding pairs not only exist but possess an alternating cycle partition where common edges form cycles of length two.

C. Classification Hierarchy

The authors present a Venn diagram (Figure 2 in the paper) classifying graphs into:

• Vertical Graphs
• Colliding Pairs (a subset of vertical graphs)
• Non-VPHT-Reconstructible Graphs (a subset of colliding pairs)
  The paper proves that for the specific constraints of "Special Colliding Pairs" (Theorem 9), the set of colliding pairs coincides with the set of non-reconstructible graphs.

4. Significance and Implications

1. Completing the Classification: While general position guarantees injectivity, this work provides the first complete characterization of injectivity failure in a degenerate setting (collinear vertices). It moves the field from "knowing it fails" to "knowing exactly when and why it fails."
2. Structural Insight: The results reveal that non-reconstructibility is not random but is strictly tied to alternating cycles and degree parity. This suggests that the VPHT "sees" the graph structure through the lens of these cycles; if two graphs can be swapped within these cycles without changing the birth/death statistics of homology features, they are indistinguishable.
3. Practical Application for Direction Selection: The authors note that their findings inform the selection of projection directions in general TDA applications. If a general graph is projected such that vertices and edges appear in an order mimicking a non-reconstructible vertical graph, the VPHT will fail to distinguish the edge set. This warns practitioners to avoid directions that induce such degeneracies.
4. Tooling: The release of the vpht-algo tool provides a resource for the community to explore VPHT properties and verify reconstructibility for small graphs, bridging the gap between abstract theory and experimental data analysis.

Conclusion

The paper successfully identifies that vertical graphs are non-VPHT-reconstructible if and only if they form a "colliding pair" characterized by alternating cycles and even vertex degrees. This work transforms the understanding of VPHT injectivity from a general position assumption to a precise structural classification, highlighting the limitations of topological summaries in degenerate geometric settings.