A C₄-Free Classification of Square Relations on Token Graphs

Abstract

A C₄-Free Classification of Square Relations on Token Graphs with girth, tree and discretization witnesses Driven by Dean A. Kulik October 2026 Abstract Let FK(X) denote the K-token graph of a finite simple graph X: vertices are the K-subsets of V(X), adjacent when their symmetric difference is an edge. Two families of 4-cycles in FK(X) arise naturally when one attaches 2-cells: the commuting squares, given by two token moves along base edges with disjoint closed supports, and all 4-cycles of the token graph. Paper I of this series showed these coincide for cycle substrates Cn with n ≥ 5. We prove the governing condition is neither a cycle hypothesis nor a girth hypothesis: 𝒦4(FK(X)) = 𝒦disj(FK(X)) ⟺ X has no subgraph isomorphic to C4, for 2 ≤ K ≤ |V(X)| − 1, the bound being necessary since the token graph degenerates to a point at K = |V|. The forward direction is a short argument on closed token walks; the converse combines the token-graph complementation Fk ≅ Fn−k with an explicit spectator construction and an exhaustive check of the finitely many small cases. Consequently girth at least 5 collapses the triangle, square and mixed relation families to one, and the bull graph — 4-cycle-free but containing a triangle — shows the triangle and square conditions are logically independent. We exhibit a 7-vertex tree whose token graph carries first cohomology of dimension 2, so configuration topology is not inherited from the base cycle space. Finally we compute the collapsed invariant on girth-≥5 substrates and partition the results by whether the discretization theorem licenses a continuous reading: at K = 2 the improved subdivision bound is what makes the identification legitimate for the Petersen graph, the Heawood graph and the tree, while the original bound fails for all three. Keywords: token graph, graph configuration space, graph braid group, discrete Morse theory, cube complex, relation layer MSC 2020: 05C76, 55R80, 20F36, 05C10 License: CC BY-NC 4.0. 1. Introduction and relation to Paper I Paper I [1] studies invariant first cohomology of a token graph relative to a declared family of 2-cells, and treats that family as a variable rather than as background. Among its results is a lemma stating that for the cycle substrate Cn with n ≥ 5, every 4-cycle of the token graph is a commuting square. That lemma is correct. It is also a special case of something that mentions no cycles. This paper isolates the general statement, proves it in both directions, and records the consequences. The results here are stated in the language of token graphs alone and do not depend on the relation-layer apparatus of [1]; readers interested only in configuration spaces of graphs may read this paper independently. Where a quantity from [1] is used — the invariant residue εharm — it is defined in §2 for completeness. The route to the general statement is worth recording because it was not a generalization found by inspection. The narrow lemma was tested against twenty substrates chosen so that they could violate it. Several did, and the pattern of failures identified the correct hypothesis: the bull, butterfly and paw satisfy the conclusion while containing triangles, ruling out girth; trees and paths satisfy it while containing no cycles at all; and K4, K5, K3,3, Q3 and C5+chord fail it, every one of them containing a 4-cycle. 2. Setting Definition 2.1. (token graph; Fabila-Monroy et al. [2]) For a finite simple graph X on n vertices and K ≥ 1, the token graph FK(X) has as vertices the K-subsets of V(X), with S adjacent to T whenever their symmetric difference is a pair of adjacent vertices of X. Equivalently, T is obtained from S by moving one token along one edge of X to an unoccupied vertex. Definition 2.2. (the two square families) A commuting square is a 4-cycle of FK(X) of the form S → (S∖{u})∪{w} → (S∖{u,v})∪{w,x} → (S∖{v})∪{x} → S, where uw and vx are edges of X whose closed supports are disjoint. The closed support of an edge uv is the vertex set it spans, written S(uv) = {u, v}; the condition is S(uw) ∩ S(vx) = ∅. Write 𝒦disj for the set of these and 𝒦4 for the set of all 4-cycles of FK(X) on four distinct vertices. Always 𝒦disj ⊆ 𝒦4. Commuting squares are exactly the 2-cells of Abrams' discretized configuration space UDK(X), whose d-cells are d base edges with pairwise disjoint closed supports together with K − d parked tokens [3]. Attaching 𝒦disj therefore builds the 2-skeleton of that complex; attaching 𝒦4 builds something strictly larger whenever the two families differ. We write εharm(𝒦) for dim H1 of the 2-complex obtained by attaching 𝒦, computed over ℚ, and εharm(𝒦 | G) for its G-invariant analogue as in [1]. 3. The classification Theorem 3.1. Let X be a finite simple graph on n vertices and let 2 ≤ K ≤ n − 1. Then 𝒦4 = 𝒦disj in FK(X) if and only if X has no subgraph isomorphic to C4, not necessarily induced. The qualification is essential and is the likeliest source of a misreading. K4 contains four-cycles as subgraphs while containing none as induced subgraphs, and it does not satisfy the equality: at K = 2 it has 15 token-graph 4-cycles of which only 3 are commuting. A reader testing the criterion with induced squares would wrongly record K4 as a counterexample. Throughout, “contains a 4-cycle” means contains a subgraph isomorphic to C4. Proof of sufficiency. Assume X is 4-cycle-free and let (A, B, C, D) be a 4-cycle of FK(X) on four distinct vertices. Traversing the loop, each token describes a closed walk in X, and the walk lengths sum to 4. No token walk has length 1, and a length-3 walk would leave a residual length of 1, so the possible partitions are {4} and {2, 2}. Suppose the partition is {4}. One token makes a closed walk of length 4 while the others are parked. Write the walk as v0 → v1 → v2 → v3 → v0 and let P be the parked set. The four token-graph vertices visited are {vi} ∪ P, so they are pairwise distinct precisely when v0, v1, v2, v3 are pairwise distinct. In that case the four consecutive base edges exhibit a subgraph isomorphic to C4, contrary to hypothesis. If instead vi = vj for some 0 ≤ i < j ≤ 3, the corresponding token-graph vertices coincide, contradicting the assumption that the cycle has four distinct vertices. Thus this case cannot occur. Suppose the partition is {2, 2}. Two tokens each traverse one base edge and return, say along uw and vx. A closed walk of length 2 traverses one edge and immediately traverses it back, so each moving token uses a single base edge twice. If one token completed its out-and-back before the other moved, the token-graph vertex at that point would equal the starting one and the cycle would lack four distinct vertices; so the two moves alternate, giving the cyclic order of Definition 2.2. The base edges must have disjoint closed supports, since a shared vertex would have to be unoccupied for one move and occupied for the other at the same step. Hence the 4-cycle is a commuting square. ∎ Proof of necessity. Assume X contains a 4-cycle on distinct vertices w, x, y, z. We produce a 4-cycle of FK(X) that is not a commuting square. First reduce to K ≤ n/2. Complementation S ↦ V(X)∖S is an isomorphism FK(X) ≅ Fn−K(X), since A and B have symmetric difference an edge precisely when their complements do; this is equation (2) of [2]. The isomorphism carries commuting squares to commuting squares, because two tokens moving along disjoint base edges correspond to two holes moving along the same two disjoint base edges. Hence 𝒦4 = 𝒦disj holds at K if and only if it holds at n − K. Now suppose n ≥ 6 and K ≤ n/2. Then n − K ≥ n/2 ≥ 3, so n ≥ K + 3 and at least K − 1 vertices of X lie outside {w, x, y, z}. Let P be a set of K − 1 such vertices and put S = {w} ∪ P. The sequence {w}∪P → {x}∪P → {y}∪P → {z}∪P → {w}∪P is a 4-cycle of FK(X) on four distinct vertices, since w, x, y, z are distinct and P is fixed and disjoint from them. Every one of its four steps moves the same token, whereas a commuting square is by Definition 2.2 built from two distinct tokens each making one out-and-back move. So it is not a commuting square. ∎ The remaining cases are n = 4 and n = 5, where no spectator set of the required size exists. These were verified exhaustively by enumeration over all labeled simple graphs on four and five vertices containing a 4-cycle — 10 and 476 graphs respectively — at every K with 2 ≤ K ≤ n − 1. No graph satisfied 𝒦4 = 𝒦disj. This is a finite computation and is stated as such; it is not covered by the spectator argument above. Remark 3.2. (the bound on K is necessary) At K = n the token graph is a single vertex with no edges, so 𝒦4 = 𝒦disj = ∅ and the equality holds vacuously for every substrate, including graphs with many 4-cycles. The hypothesis K ≤ n − 1 excludes exactly this degeneracy. 4. Girth at least 5, and the independence of the two conditions A triangle-free substrate admits no 3-cycle in its token graph: an arena 3-cycle requires three K-sets pairwise differing by one move, and whether or not a token is parked the three moves use the edges of a base triangle [1, Lemma 6.1]. Combining that with Theorem 3.1: Corollary 4.1. If girth(X) ≥ 5 and 2 ≤ K ≤ n − 1, then 𝒦3 = ∅ and 𝒦4 = 𝒦disj; hence 𝒦disj = 𝒦4 = 𝒦3,4 and the three corresponding residues agree. The two hypotheses are independent, and a single substrate separates them. The bull — a triangle with two pendant vertices — contains no 4-cycle, so Theorem 3.1 gives 𝒦4 = 𝒦disj. It does contain a triangle, and at K = 2 under its full automorphism group: εharm(𝒦disj) = εharm(𝒦4) = 3, εharm(𝒦3,4) = 0. So 4-cycle-freeness alone delivers the square collapse and not the full collapse. A control of this kind is more informative than a further positive example: it isolates which clause is doing the work rather than accumulating cases where both hold. 5. Trees: configuration topology is not inherited A natural but false heuristic holds th