Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Campbell’s group-graph reciprocal-pair conjecture

Abstract

A sign-coupled group on three edges and two four-cliques refutes the reciprocal-pair classification.

Definition 1.1 (Automorphisms).

Formalization. D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.IsAut (✓ std3).

Citation. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Commentary.

Page 4: “By definition, g is an element of the automorphism group if and only if {i, j} and {g(i), g(j)} are both edges in Γ.” The permutation preserves adjacency in both directions.

Definition 1.2 (Cycle polynomial).

Formalization. D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.cyclePoly (✓ std3).

Citation. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Commentary.

Page 1: “The cycle polynomial of a finite permutation group G acting on a set Ω of size n is” F_G(x) = Σ_{g∈G} x^{c(g)}, “where c(g) is the number of cycles (including fixed points) of g on Ω.” SameCycle identifies vertices in a common permutation cycle, including each fixed vertex as a singleton. The coefficients are integers.

Definition 1.3 (Fixed proper colourings).

Formalization. D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.fixedColourings (✓ std3).

Citation. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Commentary.

Page 1: “A proper colouring of a graph is a map from the vertex set to the set of colourings such that no two adjacent vertices have the same colour.” Page 1: “The chromatic polynomial PΓ/g(x) is the polynomial which counts proper colourings of Γ fixed by g.” Colours are Fin c; each map is counted once, with adjacent vertices differently coloured and f(g(v)) = f(v).

Definition 1.4 (Reciprocal pairs).

Formalization. D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.IsReciprocal (✓ std3).

Citation. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Commentary.

Page 2: “We call a group-graph pair (Γ, G) a reciprocal pair if the relation” PΓ,G(x) = (−1)^n F_G(−x) “holds for a simple graph Γ with n vertices and where G is an automorphism group of Γ.” The equation is evaluated at every positive natural number c. Equality at all these integers is equality of the corresponding polynomials.

Definition 1.5 (A sufficient obstruction to irreducibility).

Formalization. D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.Reducible (✓ std3).

Citation. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Commentary.

Page 3: “A reciprocal pair (Γ, G) is irreducible is there is no non-trivial decomposition Γ = Γ1 ∪ Γ2 ∪ … ∪ Γn and subgroups Gi ≤ G with Gi ≤ Aut(Γi) such that either” “1. G = G1 × … × Gn with each (Γi, Gi) a reciprocal pair,” “2. Gi ≅ Gj and Γi ≅ Γj for all i ≠ j and G = G0 ≀ H for some H ≤ Sn and G0 ≅ Gi for all i.” The displayed predicate allows more decompositions: the first branch requires only generation by subgroups fixing other parts; the second requires only isomorphism of the induced part graphs. Surjectivity and m ≥ 2 make the parts nonempty and the decomposition nontrivial.

Definition 1.6 (Irreducibility).

Formalization. D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.IsIrreducible (✓ std3).

Citation. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Commentary.

No decomposition satisfies either of the two conditions in Reducible. Since those conditions include every decomposition in the definition on page 3, this predicate implies the source’s irreducibility.

Definition 1.7 (The listed graph classes).

Formalization. D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.Listed (✓ std3).

Citation. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Commentary.

Page 3: “1. (Γ, G) is one of the two trivial cases: (a) Γ is a null graph and G is any group with no odd permutations, (b) Γ is the complete graph with n vertices and G = Sn. 2. Γ is a 4-cycle and G ≅ Aut(Γ). 3. Γ is a k-star and G is defined in Theorem 1.” The predicate drops the group restrictions and retains these four graph conditions. A k-star has a nonempty proper centre K; distinct vertices are adjacent exactly when at least one lies in K.

Definition 1.8 (The conjecture).

Formalization. D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.claim (✓ std3).

Citation. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Commentary.

Conjecture, page 3 (verbatim): “Conjecture: Let (Γ, G) be an irreducible reciprocal pair. Then one of the following hold: 1. (Γ, G) is one of the two trivial cases: (a) Γ is a null graph and G is any group with no odd permutations, (b) Γ is the complete graph with n vertices and G = Sn. 2. Γ is a 4-cycle and G ≅ Aut(Γ). 3. Γ is a k-star and G is defined in Theorem 1.” V is a finite vertex type, Gamma denotes Γ, and G is a finite subgroup of Equiv.Perm V. Automorphisms, positive-integer evaluations, irreducibility and the listed classes have exactly the meanings displayed above. The broader decomposition test and broader listed conclusion make claim a consequence of the source conjecture.

Theorem 1.9 (Refutation).

Proof. Machine-checked in Lean as D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.result (✓ std3). ∎

Resolves. Problems/campbell-2020-group-graph-reciprocal-pairs (refuted) by D5/S3/Combinatorics/ReciprocalPairs/GroupGraphReciprocalRefutation.result.

Source. Repository-derived.

Acknowledgement. Kirsty Campbell (2020). Group-Graph Reciprocal Pairs. DOI: 10.48550/arXiv.2005.13566. URL: https://arxiv.org/abs/2005.13566.

Acknowledgement. Peter J. Cameron, Jason Semeraro (2018). The cycle polynomial of a permutation group. DOI: 10.37236/7299. URL: https://arxiv.org/abs/1701.06954.

Commentary.

The graph 3K₂ ⊔ 2K₄ has fourteen vertices. The group permits all internal clique permutations, with S₃ acting on the three edges naturally and on the two four-cliques through its sign. It is reciprocal: nonproper colourings cancel under an edge transposition, while every permutation fixing a proper colouring has sign +1. Its two clique layers cannot generate the whole coupled group from subgroups supported on separate parts. Pairwise isomorphic parts would have equal even cardinalities, which is incompatible with fourteen vertices and between two and five parts. An edge and a nonedge exclude the two trivial graph classes, cardinality excludes the four-cycle, and the absence of a universal vertex excludes every k-star. The general cycle-polynomial and reciprocity background is Cameron–Semeraro (2018).

References