Cohomological k-Equivalence Does Not Capture Graph Isomorphism: A negative answer to Question 14 of Ó Conghaile
Ó Conghaile introduced cohomological k-equivalence, a refinement of equivalence in k-variable counting logic that is decidable in polynomial time for each fixed k: the local isomorphisms that survive must extend, in both directions, to compatible families of integer combinations of local isomorphisms. He asked whether, for every finite relational signature σ, some k makes cohomological k-equivalence coincide with isomorphism of σ-structures (Question 14 of his MFCS 2022 paper). We show that the answer is negative already for graphs: for every k ≥ 1 there are finite simple graphs A_k and B_k that are not isomorphic but are cohomologically k-equivalent. Every isomorphism of the pair would induce a permutation g of a common index set D. One part of the graphs, over F_3, admits exactly the even permutations, because g acts by its sign on a nonzero class in the cokernel of the unsigned boundary map on subsets of D. A second part, over F_2 and built on the Johnson graph J(|D|,2), admits exactly the odd permutations. No set of at most k vertices detects the parity: every local isomorphism of a common family is realised, with the same images, by permutations of both parities. For each local isomorphism we build two compatible families of local distributions, one for each parity, whose denominators are powers of 2 and of 3 respectively. As in the Diophantine lower bound of Berkholz and Grohe, a Bézout combination yields integral extensions, while the nonnegative average yields the bijective forth property. The graphs have size doubly exponential in k. We complement the main result with three observations. For the pair built from an index set of size n, the least width at which cohomological equivalence distinguishes the two graphs is log_4 n + O(1). So within this construction the doubly exponential size is unavoidable. The pairs are nevertheless distinguished in polynomial time by an explicit invariant that combines the class of the part over F_3 with the parity of the part over F_2. Finally, cohomological 2-equivalence already distinguishes the coloured graphs with which Berkholz and Grohe show that no level of the Diophantine relaxation decides isomorphism.
Authors
- Asterios Gkantzounis
Institutions
- Technical University of Crete (GR)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-19
- DOI
- https://doi.org/10.5281/zenodo.24373439
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint