Relation Algebra Representations from Distance-Regular Graphs
Pith reviewed 2026-05-15 01:43 UTC · model grok-4.3
The pith
The relation algebra 30_65 has a finite representation on 42 points from the Hoffman-Singleton graph.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Given a distance-regular graph of diameter d, the d+1 distance relations (including the equality relation) form the atoms of an integral symmetric relation algebra on the vertex set. This representation is algebraic if and only if the graph is distance-transitive. For diameter 3 the mandatory cycle condition is expressed directly in terms of the intersection array. The second subconstituent of the Hoffman-Singleton graph therefore gives a representation of 30_65 on 42 points, an infinite family of representations for 26_65, and the smallest known representation for 31_65.
What carries the argument
The distance coloring of the complete graph on the vertices of a distance-regular graph, which partitions pairs into d+1 atoms whose composition is governed by the graph's intersection numbers.
If this is right
- Every distance-transitive graph produces an algebraic representation of its distance algebra.
- For diameter-3 graphs the check that the representation is valid reduces to verifying a single numerical condition on the intersection array.
- The same construction yields an infinite family of finite representations for 26_65.
- The smallest finite representation of 31_65 arises from this distance-graph method.
Where Pith is reading between the lines
- Enumerating small intersection arrays could locate additional finite representations for other open relation algebras.
- The same distance-coloring idea may extend to other distance-regular objects such as association schemes or coherent configurations.
- The equivalence between algebraicity and distance-transitivity suggests a broader correspondence between symmetry properties of graphs and algebraic properties of their relation algebras.
Load-bearing premise
The constant intersection numbers of a distance-regular graph automatically ensure that the composition of any two distance relations is a fixed linear combination of the remaining distance relations, satisfying all relation-algebra axioms.
What would settle it
A direct count of common neighbors for pairs of given distances in the 42-point Hoffman-Singleton subconstituent that fails to match the composition table of 30_65 would show the induced structure is not a representation.
read the original abstract
We describe a general method for constructing representations of finite integral symmetric relation algebras from distance-regular graphs. Given a distance-regular graph of diameter $d$, the distances between vertices induces a coloring of the complete graph with $d$ colors, and we show that this coloring yields a representation of finite integral symmetric relation algebra on $d+1$ atoms. We then introduce a necessary and sufficient condition for when such a representation is algebraic, proving that this occurs if and only if the distance-regular graph is also distance-transitive. We study the diameter-3 case of this method in detail, and we express a condition for the representation's mandatory cycles in terms of the distance-regular graph's intersection array. We apply this result to give a positive answer to an open question of Roger Maddux; namely, whether the relation algebra $30_{65}$ has a representation on a finite set. The representation is given on 42 points, and arises from the second subconstituent of the Hoffman-Singleton graph. We further use this method to describe an infinite class of finite representations of $26_{65}$ and the smallest possible representation of $31_{65}$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents a general construction of representations for finite integral symmetric relation algebras from distance-regular graphs of diameter d, where the d distance relations on the vertex set induce a representation on d+1 atoms. It proves that the representation is algebraic if and only if the graph is distance-transitive. For the diameter-3 case, a condition on mandatory cycles is expressed in terms of the intersection array. The main application resolves an open question of Maddux by exhibiting a representation of the algebra 30_65 on 42 points arising from the second subconstituent of the Hoffman-Singleton graph; additional results include an infinite family of finite representations for 26_65 and the smallest representation for 31_65.
Significance. If the proofs hold, the work supplies a systematic combinatorial source of finite representations for relation algebras and directly answers a longstanding open question on the finite representability of 30_65. The equivalence between algebraicity and distance-transitivity, together with the explicit intersection-array criterion for diameter 3, links association schemes to relation-algebra representability in a way that may generate further examples. The infinite family for 26_65 and the concrete 42-point model are concrete strengths.
major comments (2)
- §4 (diameter-3 case) and the application to 30_65: the manuscript must supply the explicit intersection array of the second subconstituent of the Hoffman-Singleton graph and verify that it satisfies the mandatory-cycle condition derived from the array; without this arithmetic check the positive answer to Maddux’s question for the 42-point model remains unconfirmed.
- Theorem 2.3 (general construction): the claim that the distance coloring always yields a representation of the (d+1)-atom algebra requires an explicit check that the composition table defined by the intersection numbers satisfies the relation-algebra axioms (in particular associativity); while the construction is standard for association schemes, the paper should state the precise axiom verifications rather than treating them as immediate.
minor comments (3)
- The abstract introduces “mandatory cycles” without a one-sentence definition; a brief gloss in the introduction would improve readability for readers outside the immediate subfield.
- Notation for the atoms (e.g., R_0, …, R_d) should be cross-referenced to the standard numbering used in Maddux’s tables for 30_65, 26_65 and 31_65 to facilitate comparison.
- A small illustrative example (e.g., the cycle graph C_5 or the Petersen graph) showing the explicit relation table produced by the construction would help readers verify the general method before the diameter-3 case.
Simulated Author's Rebuttal
We thank the referee for the careful reading, positive evaluation, and constructive suggestions. The comments identify places where additional explicit details will improve clarity and verifiability. We address each point below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: §4 (diameter-3 case) and the application to 30_65: the manuscript must supply the explicit intersection array of the second subconstituent of the Hoffman-Singleton graph and verify that it satisfies the mandatory-cycle condition derived from the array; without this arithmetic check the positive answer to Maddux’s question for the 42-point model remains unconfirmed.
Authors: We agree that the explicit intersection array and the direct verification of the mandatory-cycle condition are necessary for a self-contained confirmation of the 42-point representation. In the revised manuscript we will insert the intersection array of the second subconstituent of the Hoffman-Singleton graph together with the arithmetic check that it meets the diameter-3 mandatory-cycle criterion derived in §4. This addition will make the positive answer to Maddux’s question fully explicit. revision: yes
-
Referee: Theorem 2.3 (general construction): the claim that the distance coloring always yields a representation of the (d+1)-atom algebra requires an explicit check that the composition table defined by the intersection numbers satisfies the relation-algebra axioms (in particular associativity); while the construction is standard for association schemes, the paper should state the precise axiom verifications rather than treating them as immediate.
Authors: We accept that a concise but explicit verification of the relation-algebra axioms, especially associativity of the composition operation induced by the intersection numbers, will make the argument more accessible. In the revision we will add a short paragraph (or short subsection) immediately after the statement of Theorem 2.3 that records the direct verification: the intersection numbers of a distance-regular graph define an association scheme, whose Bose-Mesner algebra is closed under matrix multiplication, and the resulting composition table therefore satisfies the relation-algebra axioms, including associativity. We will also note the standard reference to the theory of association schemes for readers who wish to consult the general background. revision: yes
Circularity Check
Minor self-citation not load-bearing; derivation is a direct construction
full rationale
The paper defines a general construction: given any distance-regular graph of diameter d, the distance relations on its vertices induce a (d+1)-atom integral symmetric relation algebra representation via the standard association-scheme correspondence. The algebraic condition is stated as necessary and sufficient in terms of the intersection array (a graph-theoretic invariant independent of the target algebra). The 30_65 representation is obtained by plugging the known parameters of the Hoffman-Singleton second subconstituent into this construction and verifying the mandatory-cycle condition; no parameter is fitted to the algebra itself, no term is defined circularly in terms of the output, and no load-bearing premise rests on a self-citation chain. The derivation therefore remains self-contained against external graph-theoretic benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption A distance-regular graph of diameter d induces a partition of the edges of the complete graph into d+1 classes (including the identity) that satisfy the relation algebra composition rules.
- domain assumption The resulting structure is integral and symmetric when the graph is distance-regular.
Reference graph
Works this paper leans on
-
[1]
Jeremy F. Alm and Eli Atkins. Algebraic representations of small relation algebras.In progress
-
[2]
Alm, Ashlee Bostic, Claire Chenault, Kenyon Coleman, and Chesney Culver
Jeremy F. Alm, Ashlee Bostic, Claire Chenault, Kenyon Coleman, and Chesney Culver. Cyclic group spectra for some small relation algebras. InRelational and algebraic methods in computer science, volume 14787 ofLecture Notes in Comput. Sci., pages 19–27. Springer, Cham, [2024] ©2024
work page 2024
-
[3]
Jeremy F. Alm and Roger D. Maddux. Finite representations for two small relation algebras. Algebra Universalis, 79(4):Paper No. 87, 4, 2018
work page 2018
-
[4]
Jeremy F. Alm, Roger D. Maddux, and Jacob Manske. Chromatic graphs, Ramsey numbers and the flexible atom conjecture.Electron. J. Combin., 15(1):Research paper 49, 8, 2008
work page 2008
-
[5]
Hajnal Andr´ eka and Roger D. Maddux. Representations for small relation algebras.Notre Dame J. Formal Logic, 35(4):550–562, 1994
work page 1994
-
[6]
A. E. Brouwer, A. M. Cohen, and A. Neumaier.Distance-regular graphs, volume 18 ofErgeb- nisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1989
work page 1989
-
[7]
Stephen D. Comer. A new foundation for the theory of relations.Notre Dame J. Formal Logic, 24(2):181–187, 1983
work page 1983
-
[8]
Stephen D. Comer. Combinatorial aspects of relations.Algebra Universalis, 18(1):77–94, 1984
work page 1984
-
[9]
Maddux.Relation algebras, volume 150 ofStudies in Logic and the Foundations of Mathematics
Roger D. Maddux.Relation algebras, volume 150 ofStudies in Logic and the Foundations of Mathematics. Elsevier B. V., Amsterdam, 2006
work page 2006
-
[10]
Leonard H. Soicher. Yet another distance-regular graph related to a Golay code.Electron. J. Combin., 2:Note 1, approx. 4, 1995
work page 1995
-
[11]
Edwin R. van Dam, Jack H. Koolen, and Hajime Tanaka. Distance-regular graphs.Electron. J. Combin., DS22:156, 2016. 19
work page 2016
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.