trureturing — Discovering truth

bibkey: daviesmarigliano2021symmetries
authors: Isobel Davies and Orlando Marigliano
year: 2021
title: Coloured Graphical Models and their Symmetries
doi: null
url: https://arxiv.org/abs/2012.01905v5
claim: "Conjecture 4.4 equates full-automorphism unordered-pair orbit counts and distinct adjacency eigenvalue counts for every uncoloured circulant graph."
strata_touched:
  - D5/S3/Combinatorics/Hamming/DaviesMariglianoCirculantOrbits
license: citation-only
triage: anchor

Verified locator

Source: https://arxiv.org/abs/2012.01905v5

Source statements

Section 4, Conjecture 4.4, PDF page 11 (Conjecture 9 in the HTML):

If $G$ is an uncoloured circulant graph, then the number of orbits of the action of $\mathrm{Aut}(G)$ on the set $V\ast V$ of unordered pairs of vertices of $G$ coincides with the number of distinct eigenvalues of its adjacency matrix.

The preceding definition on page 11 reads:

By definition, these are graphs that have a symmetry which is a cyclic permutation of its vertices.

Corollary 3.3, PDF page 7, specifies the action:

In particular, let $V\ast V$ be the set of unordered pairs of vertices of $G$ and $s$ the number of orbits of the entrywise action of $\mathrm{Aut}(G)$ on $V\ast V$.

Its proof specifies that the number of elements in $V\ast V$ is $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$; diagonal pairs are included. The automorphism group is the full group, rather than the subgroup generated by a cyclic symmetry. The real symmetric adjacency matrix has entries one at adjacent vertices and zero elsewhere; distinct scalar eigenvalues are counted without multiplicity.

Counterexample and scope

The thirty-vertex graph whose residues modulo 2, 3 and 5 disagree in exactly one coordinate is circulant. The Lean result proves at least eight unordered-pair orbits under its full automorphism group and at most seven distinct real adjacency eigenvalues. These bounds refute the universal equality; exact counts and infinite-family extensions are not separate Lean assertions here.

The exact experimental counts, source quotations and literature screen are specified in issue #21260. The experiment is in the-omega-institute/trureturing-experiments, commit bc7eba4d10d7a9ada06fcabe82de3d2bae5ee2f4, at docs/reports/davies-marigliano-2021-circulant-orbit-eigenvalue-conjecture/check.py, SHA-256 97dbbc1e143d34eab4bd06fb441e38cb19bd71202ccc50c09af55d0ff9b73c2d; its reported execution exited 0. No program text is reproduced here.

Literature boundary

Literature completeness is ASSUMED-UNVERIFIED. The three Beezer originals listed in issue #21260 remain unread, and the citation APIs did not yield a complete inventory. No priority claim is made. This note uses the arXiv v5 text; equivalence with the journal text and the cited journal DOI has not been independently verified.