Description
A graph-based code whose generator matrix is the row space of the adjacency matrix of the Higman-Sims graph, yielding a \([100,22,22]\) code \(C_{HS}\) whose dual is a \([100,78,6]\) code [1; Table IV].
A related \([100,22,32]\) code \(C_{100}\), invariant under the Higman-Sims simple group \(HiS\), is obtained by restricting a \([176,22,50]\) code invariant under the simple group \(Co_3\) [3] to the 100 nonzero coordinates of a fixed minimum-weight codeword. Its dual is an optimal \([100,78,8]\) code [1; Table VI]. The full automorphism groups are \(\mathrm{Aut}(C_{HS}) = 2\cdot HiS\) and \(\mathrm{Aut}(C_{100}) = HiS\) [1; Rem. 1.5]. The codes \(C_{HS}\) and \(C_{100}\) intersect in their doubly-even-weight subcodes, which have dimension 21 [1; Rem. 1.5].
Decoding
The rows of the adjacency matrix can be used as orthogonal parity checks enabling majority decoding of \(C_{HS}^\perp\) up to two errors [1; Prop. 1.4].Cousins
- Combinatorial design— The 4125 codewords of weight 36 of the \([100,22,32]\) code \(C_{100}\) form a \(2\)-\((100,36,525)\) design, which can be used for majority decoding of single errors in \(C_{100}^\perp\) [1; Rem. 1.7].
- \(\Lambda_{24}\) Leech lattice— The Higman-Sims graph occurs in the Leech lattice [4].
- Two-point homogeneous-space code— The Higman-Sims graph is distance-transitive, hence it is a finite two-point homogeneous space [5].
Primary Hierarchy
References
- [1]
- V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
- [2]
- V. D. Tonchev, “Error-correcting codes from graphs”, Discrete Mathematics 257, 549 (2002) DOI
- [3]
- W. H. Haemers, C. Parker, V. Pless, and V. D. Tonchev, “A design and a code invariant under the simple group \(Co_3\),” J. Comb. Theory, vol. A 62, pp. 225–233, 1993.
- [4]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [5]
- A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs (Springer Berlin Heidelberg, 1989) DOI
Page edit log
- Andrey Boris Khesin (2025-01-31) — most recent
- Victor V. Albert (2025-01-31)
- Victor V. Albert (2024-03-21)
Cite as:
“Higman-Sims graph-adjacency code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2025. https://errorcorrectionzoo.org/c/higman-sims_graph