Source-linked AI summary
Graphs with Long Pseudosimilarity Chains under Consecutive Vertex Deletions
Sergey Ivanov
TL;DR
The paper asks how long pseudosimilarity can persist under consecutive deletions, rather than merely how many pseudosimilar vertices a graph can contain. It defines pseudosimilarity depth and uses broken hidden cyclic orbits to construct connected graphs with asymptotically full active chains, including asymmetric intermediate graphs.
Problem
The paper investigates the unexplored recursive question of how many successive deletions can remain active when each deleted vertex is pseudosimilar at that moment.
Method
The authors define pseudosimilarity depth and construct chains by breaking hidden cyclic automorphism orbits with one or multiple clocks.
Results
The maximum pseudosimilarity depth is asymptotic to graph order; an infinite family also keeps the starting and intermediate graphs asymmetric.
Takeaways & Limitations
Pseudosimilarity can persist through an asymptotically full sequence of deletions even when every graph encountered in the main chain is asymmetric.
Takeaways & Limitations
The gap between the elementary upper bound and the lower bounds remains substantial, including whether the polylogarithmic remainder can be reduced to a constant.
Abstract
from arXiv · showhide
Pseudosimilar vertices are vertices in distinct automorphism orbits whose deletions produce isomorphic graphs. Classical work has studied the existence, group-theoretic origin, and construction of large sets of such vertices. We ask a different recursive question: how long can one repeatedly delete a vertex that is pseudosimilar at the moment of deletion? We define the pseudosimilarity depth of a graph and construct connected graphs in which this process continues through all but a sublinear number of vertices. A two-clock construction gives a square-root deficit uniformly in the order, while a Chinese-remainder construction with many cyclic clocks yields an infinite family of asymmetric graphs with only a polylogarithmic number of vertices left outside the active chain. The mechanism realizes pseudosimilarity by breaking a long hidden automorphism orbit and enlarging the break one vertex at a time. Thus pseudosimilarity can persist through an asymptotically full sequence of vertex deletions, even though every graph encountered in the main construction is asymmetric.
1 Introduction
The paper shifts pseudosimilarity research from static constructions to recursive deletion chains, introducing pseudosimilarity depth to measure how long active deletions can continue. Its constructions show depth asymptotic to graph order, including asymmetric intermediate graphs.
- Motivation: The paper asks whether successive vertex deletions can remain active, extending the static study of pseudosimilar vertices into a recursive setting.Earlier work focused mainly on how many pseudosimilar vertices can coexist or how such sets arise.
- Contribution: Pseudosimilarity depth psd(G) is the maximum number of consecutive active deletions starting from G.A deletion is active when the deleted vertex has a pseudosimilar mate at that moment.
- Results: For all sufficiently large n, the maximum depth is asymptotically as large as the graph itself, so PS(n)/n →1.The basic-bound graphs are connected.
- Results: An infinite family has connected asymmetric starting graphs whose every intermediate graph in the active chain is asymmetric.This shows recursive pseudosimilarity need not rely on automorphisms surviving in the graphs being traversed.
- Mechanism: The construction uses a hidden cyclic orbit: deleting a consecutive interval breaks automorphisms while preserving removal-similarity at the gap endpoints.Two relatively prime clocks produce a square-root deficit, while many clocks and the Chinese remainder theorem reduce the auxiliary part to polylogarithmic size.
2 Active deletion chains
This section formalizes active deletion chains and pseudosimilarity depth, emphasizing that the deleted vertex must itself participate in the ambiguity. A sliding-gap lemma supplies the removal-similarity mechanism behind the constructions.
- Definitions: An active pseudosimilarity chain is a sequence of distinct vertices where each next vertex has a pseudosimilar mate in the graph reached after earlier deletions.The definition starts with G0 = G and updates the graph after each deletion.
- Definitions: psd(G) is the maximum length of an active pseudosimilarity chain in G.The extremal function PS(n) maximizes psd(G) over graphs of order n.
- Definitions: The active condition prevents arbitrary padding: the vertex deleted at every step must participate in the deletion ambiguity.Merely retaining a pseudosimilar pair while deleting unrelated vertices would make long sequences immediate.
- Bounds: A graph with a pseudosimilar pair requires at least eight vertices, and the paper aims to show this elementary lower bound is nearly attainable asymptotically.The classical eight-vertex example is attributed to Harary and Palmer.
- Sliding-gap mechanism: The sliding-gap lemma states that in Gi = H −{x0, . . . , xi−1}, the vertices xi and xL−1 are removal-similar.The vertices lie on a cyclic orbit of an automorphism of H.
3 A 17-vertex example
The 17-vertex example instantiates the clock construction with a broken six-cycle orbit. Four successive deletions are active while each current graph remains connected and asymmetric.
- Construction: The construction uses a 6-cycle of a-vertices, an independent inner layer of b-vertices, and pendant x-vertices attached individually to the a-vertices.Deleting x0 creates the initial gap and leaves the 17-vertex graph G1.
- Verification: G1, G2, G3, and G4 are connected and asymmetric, while xi and x5 are pseudosimilar in Gi for i = 1, 2, 3, 4.The active pairs are (x1, x5), (x2, x5), (x3, x5), and (x4, x5).
- Result: The chain x1, x2, x3, x4 gives four active deletions, establishing psd(G1) ≥4.This is the smallest instance of the clock construction, not a claim of global minimality for depth four.
- Mechanism: Each deletion moves one endpoint of the missing-leaf break, producing a card isomorphic to the card obtained by deleting the fixed vertex x5.The break destroys the hidden cyclic automorphism while preserving the relevant card isomorphism.
4 One cyclic clock
The one-clock construction attaches indexed vertices to a cyclic graph so that deleting a consecutive block leaves a long active pseudosimilarity chain, while each intermediate graph remains asymmetric.
- Clock construction: Q_m is an m-clock whose A-vertices form a cycle and whose independent B-vertices have neighborhoods {a_i, a_{i+1}, a_{i+3}}.Its cyclic symmetry is generated by simultaneously rotating the A- and B-vertices.
- Clock construction: Adding one indexed vertex to each clock position produces H_m, with the clock rotation extended by x_i 7→x_{i+1}.The indexed vertices are attached independently to corresponding clock positions.
- Active chain: The one-clock construction gives linear depth, but only about one third of its vertices are active.The later two-clock construction targets this overhead by encoding each active vertex simultaneously on two clocks.
5 Two clocks and a square-root deficit
The two-clock construction combines coprime cyclic clocks so indexed vertices occupy product-many positions, yielding long active chains in connected asymmetric graphs and a square-root deficit uniformly in order.
- Construction: Two coprime clocks Q_p and Q_q are combined with indexed vertices attached according to residues modulo p and q.Simultaneously rotating both clocks and shifting the indexed vertices gives an automorphism of order L.
- Asymptotic bound: Taking consecutive integers already gives the advertised square-root deficit.The product of the clock lengths grows quadratically relative to their summed auxiliary structure.
- Uniformity: Join padding preserves active pseudosimilarity chains when the underlying graphs and all intermediate graphs have no universal vertex.The clock graphs satisfy this condition throughout the chain.
- Uniformity: There is an absolute constant C such that, for all sufficiently large n, a connected n-vertex graph achieves the uniform asymptotic depth bound.The supplied theorem statement gives the existence claim but not the displayed bound value.
6 Many clocks and a polylogarithmic deficit
The many-clock construction uses several cyclic moduli and Chinese-remainder indexing to enlarge the active chain relative to its overhead, producing infinitely many connected asymmetric examples with polylogarithmic deficit.
- Construction: Vertices x_k are attached to one position on each of r disjoint clocks according to k modulo each clock modulus.The resulting graph deletes x_0 through x_{i−1} to form G_i.
- Many-clock chain: Every G_i is connected and asymmetric, and x_i is pseudosimilar to x_{L−1} for 1 ≤ i ≤ L−2.Thus the chain remains active across the indexed deletions.
- Asymptotic result: Every graph encountered in this active chain is asymmetric.The construction therefore maintains asymmetry while pseudosimilar deletions continue.
- Construction: Small distinct prime moduli make the product of clock lengths much larger than their sum.This product-versus-sum separation is the arithmetic basis for reducing the deficit.
- Asymptotic result: There is an infinite sequence of connected asymmetric graphs with a polylogarithmic deficit.Every intermediate graph in the corresponding active chain is also connected and asymmetric.
7 Relation to earlier pseudosimilarity constructions
The paper distinguishes recursive active deletion chains from classical constructions of large mutually pseudosimilar sets, minimal pseudosimilarity, and cross-graph card overlap.
- Hidden automorphisms: The construction instantiates the group-theoretic picture in which a hidden cyclic orbit is partially deleted, leaving successive deletion equivalences.A single cyclic supergraph explains the entire chain simultaneously.
- Mutual pseudosimilarity: Classical work seeks many vertices in one graph that are pairwise deletion-equivalent and lie in distinct automorphism orbits.The present chain may have only one distinguished pseudosimilar pair at each level; its large quantity is the number of active levels.
- Minimality: The recursive question studied here is opposite to minimal pseudosimilarity: it asks whether deletion can repeatedly move to a proper card while retaining active ambiguity.The paper frames high depth as repeated persistence rather than minimal containment.
- Related parameters: Pseudosimilarity depth differs from deck overlap and reconstruction numbers because it concerns nested cards of one graph rather than many cards shared by different graphs.Both settings use a small structural core to control deletion equivalences, but they measure different objects.
8 Open problems
The paper closes by identifying unresolved questions about tightening the depth bound, restricting graph classes, and understanding the structure behind long active chains.
- The polylogarithmic remainder might be reducible to a constant, but the current gap from the elementary upper bound remains substantial.Achieving a constant remainder would require a mechanism different from the clock construction.
- It remains open whether a cyclic motion of very large order can be realized with less auxiliary overhead than the many-clock architecture.For squarefree L, the construction reflects a sum-versus-product trade-off using prime-divisor clock sizes.
- The maximum pseudosimilarity depth is open for trees, planar graphs, bounded-degree graphs, and regular graphs.The present construction uses cycles and vertices of growing degree, so it does not address trees.
- A further question is whether linear depth forces a common ambient automorphism to generate a positive fraction of the active chain.The alternative is that long chains could arise from unrelated local pseudosimilarities at successive levels.
9 Conclusion
The conclusion frames pseudosimilarity as a recursive deletion ambiguity rather than only a static relation between vertices. Broken cyclic orbits generate active chains whose inactive remainder can shrink from linear to square-root and then polylogarithmic order.
- A broken cyclic orbit lets deleting one gap endpoint move the graph to the next level while preserving pseudosimilarity with a fixed vertex.This supplies the mechanism for iterating the ambiguity through consecutive deletions.
- One clock gives a linear construction, two clocks reduce the inactive part to square-root order, and many relatively prime clocks reduce it to polylogarithmic order.
- The maximum pseudosimilarity depth is asymptotic to the full graph order.The conclusion presents recursive deletion ambiguity as more abundant than the static viewpoint suggests.
A Deferred proofs
The deferred-proof appendix collects proofs omitted from the main text in the order in which their statements appear.
- All proofs omitted from the main text are collected in statement order.
A.1 Proof of the elementary upper bound
The appendix establishes the elementary upper bound and verifies the clock constructions, including connectivity, removal-similarity, asymmetry, and their depth estimates.
- A.1 Proof of the elementary upper bound: At most n −7 active deletions can occur because the graph immediately before the final deletion must contain a pseudosimilar pair, requiring at least eight vertices.
- A.3 Verification of the 17-vertex example: In the one-clock example, deleting x_i or x_5 produces isomorphic cards because the deleted interval shifts by one position.
- A.3 Verification of the 17-vertex example: The one-clock graphs are asymmetric because degree classes are preserved and the surviving cyclic interval has trivial translation stabilizer.
- A.4 One-clock chain: Deleting x_1 through x_m−2 in order gives an active chain of length m−2, with x_m−1 serving as the pseudosimilar mate throughout.
- A.5 Two-clock construction: For two clocks, distinct clock orders prevent interchange, while the Chinese remainder theorem combines their rotations into one translation whose trivial interval stabilizer forces asymmetry.