Multiplicable walk posets: a two-fold automorphism criterion, the dodecahedron, and the triangular graph T(6)

Abstract

The walk poset P(G,v₀) of a finite graph G with base point v₀ has as elements the pairs (v,m) joined to v₀ by a walk of length m, ordered by the existence of a walk realising the rank difference. For vertex-transitive G it is a finite-type ℕ-graded upho poset, and Matsuoka used it to refute the conjecture of Fu, Peng and Zhang that every finitary upho poset is multiplicable: P(Petersen,v₀) is not. He then asked for which finite vertex-transitive graphs P(G,v₀) is multiplicable. Matsuoka's negative machinery rests on a spectral rigidity lemma, which forces every pair of bijections (φ,psi) with u ∼ w ⇔ φ u ∼ psi w to be diagonal and therefore applies only to graphs whose spectrum contains no pair ± λ. We remove that hypothesis. Our main theorem shows that a multiplication on P(G,v₀) produces a twisted regular representation: a regular section of the group Γ of two-fold automorphisms of G whose partner family is conjugate back into it. Only symmetry of the adjacency relation, twin-freeness, and stabilisation of the rank sets are used—neither vertex-transitivity nor connectivity. Since a twisted regular representation is a finite object, non-multiplicability becomes decidable by a finite search whose completeness is proved rather than assumed. We apply this to the dodecahedron, where Γ has 240 elements against |Aut| = 120: P(Dodecahedron,v₀) is not multiplicable, and it is a cell that Matsuoka's spectral criterion provably cannot reach, the adjacency matrix being singular. On the positive side we show that P(T(6),v₀) is multiplicable for the triangular graph T(6)=L(K₆)=J(6,2), which is neither a Cayley graph nor spectrally accessible, and we reprove Matsuoka's positive result for L(Petersen) from a single regular subgroup instead of a solver-found table. Fifteen of the sixteen graphs of a reference catalogue are thereby decided. Every statement is machine-checked in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   8b52cd7123ecdc2477a008c7820009186366a00441083daea742b5083cc2593b