Neighbour-transitive codes in Kneser graphs. (English) Zbl 1536.05478
Summary: A code \(C\) is a subset of the vertex set of a graph and \(C\) is \(s\)-neighbour-transitive if its automorphism group \(\operatorname{Aut}(C)\) acts transitively on each of the first \(s + 1\) parts \(C_0, C_1, \ldots, C_s\) of the distance partition \(\{C = C_0, C_1, \ldots, C_{\rho}\}\), where \(\rho\) is the covering radius of \(C\). While codes have traditionally been studied in the Hamming and Johnson graphs, we consider here codes in the Kneser graphs. Let \(\Omega\) be the underlying set on which the Kneser graph \(K(n, k)\) is defined. Our first main result says that if \(C\) is a 2-neighbour-transitive code in \(K(n, k)\) such that \(C\) has minimum distance at least 5, then \(n = 2k+1\) (i.e., \(C\) is a code in an odd graph) and \(C\) lies in a particular infinite family or is one particular sporadic example. We then prove several results when \(C\) is a neighbour-transitive code in the Kneser graph \(K(n, k)\). First, if \(\operatorname{Aut}(C)\) acts intransitively on \(\Omega\) we characterise \(C\) in terms of certain parameters. We then assume that \(\operatorname{Aut}(C)\) acts transitively on \(\Omega\), first proving that if \(C\) has minimum distance at least 3 then either \(K(n, k)\) is an odd graph or \(\operatorname{Aut}(C)\) has a 2-homogeneous (and hence primitive) action on \(\Omega\). We then assume that \(C\) is a code in an odd graph and \(\operatorname{Aut}(C)\) acts imprimitively on \(\Omega\) and characterise \(C\) in terms of certain parameters. We give examples in each of these cases and pose several open problems.
MSC:
| 05E18 | Group actions on combinatorial structures |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 20B25 | Finite automorphism groups of algebraic, geometric, or combinatorial structures |
| 94B25 | Combinatorial codes |
Software:
GAPReferences:
| [1] | Bailey, R. F.; Hawtin, D. R., On the classification of binary completely transitive codes with almost-simple top-group, Eur. J. Comb., 107, Article 103604 pp. (2023) · Zbl 1506.94099 |
| [2] | Bamberg, J.; Devillers, A.; Ioppolo, M.; Praeger, C. E., Codes and designs in Johnson graphs from symplectic actions on quadratic forms (2022), arXiv preprint |
| [3] | Biggs, N., Perfect codes in graphs, J. Comb. Theory, Ser. B, 15, 3, 289-296 (1973) · Zbl 0256.94009 |
| [4] | Borges, J.; Rifà, J.; Zinoviev, V. A., Nonexistence of completely transitive codes with error-correcting capability \(e > 3\), IEEE Trans. Inf. Theory, 47, 4, 1619-1621 (2001) · Zbl 1017.94015 |
| [5] | Borges, J.; Rifà, J.; Zinoviev, V. A., On completely regular codes, Probl. Inf. Transm., 55, 1, 1-45 (2019) · Zbl 1452.94133 |
| [6] | Conway, J. H., Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups (1985), Clarendon Press · Zbl 0568.20001 |
| [7] | Crnković, D.; Hawtin, D. R.; Švob, A., Neighbour-transitive codes and partial spreads in generalised quadrangles, Des. Codes Cryptogr., 90, 1521-1533 (2022) · Zbl 1495.94142 |
| [8] | Crnković, D.; Crnković, V. Mikulić; Švob, A., Block designs and strongly regular graphs admitting a transitive action of the Mathieu group \(M_{11}\), Australas. J. Comb., 73, 149-161 (2019) · Zbl 1419.05030 |
| [9] | Crnković, D.; Švob, A., Transitive t-designs and strongly regular graphs constructed from linear groups \(L(2, q), q \leq 23\), Int. J. Group Theory, 8, 43-64 (2019) · Zbl 1443.05020 |
| [10] | Delsarte, P., An Algebraic Approach to the Association Schemes of Coding Theory (1973), N. V. Philips’ Gloeilampenfabrieken, Philips Research Reports: Supplements · Zbl 1075.05606 |
| [11] | Dixon, J. D.; Mortimer, B., Permutation Groups, vol. 163 (1996), Springer: Springer New York · Zbl 0951.20001 |
| [12] | Durante, N., On sets with few intersection numbers in finite projective and affine spaces, Electron. J. Comb., 4-13 (2014) · Zbl 1298.05049 |
| [13] | The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.11.1 (2021) |
| [14] | Gillespie, N. I.; Praeger, C. E., Characterisation of a family of neighbour transitive codes (2014), Preprint |
| [15] | Giudici, M.; Praeger, C. E., Completely transitive codes in Hamming graphs, Eur. J. Comb., 20, 7, 647-662 (1999) · Zbl 0943.05042 |
| [16] | Godsil, C.; Royle, G. F., Algebraic Graph Theory, vol. 207 (2013), Springer Science & Business Media |
| [17] | Hawtin, D. R.; Praeger, C. E., Minimal binary 2-neighbour-transitive codes, J. Comb. Theory, Ser. A, 171 (2020) · Zbl 1467.94050 |
| [18] | Huang, He; Xia, Binzhou; Zhou, Sanming, Perfect codes in Cayley graphs, SIAM J. Discrete Math., 32, 1, 548-559 (2018) · Zbl 1381.05032 |
| [19] | Krotov, D. S., Perfect codes in Doob graphs, Des. Codes Cryptogr., 80, 1, 91-102 (2016) · Zbl 1348.94082 |
| [20] | Liebler, R. A.; Praeger, C. E., Neighbour-transitive codes in Johnson graphs, Des. Codes Cryptogr., 73, 1, 1-25 (2014) · Zbl 1296.05089 |
| [21] | Neunhöffer, M.; Praeger, C. E., Sporadic neighbour-transitive codes in Johnson graphs, Des. Codes Cryptogr., 72, 1, 141-152 (2014) · Zbl 1294.05093 |
| [22] | Witt, E., Die 5-fach transitiven gruppen von Mathieu, Abh. Math. Semin. Univ. Hamb., 12, 256-264 (1938) · JFM 64.0963.01 |
| [23] | Witt, E., Über steinersche systeme, Abh. Math. Semin. Univ. Hamb., 12, 265-275 (1938) · JFM 64.0937.02 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
