×

On intersection density of transitive groups of degree a product of two odd primes. (English) Zbl 1514.20016

Summary: Two elements \(g\) and \(h\) of a permutation group \(G\) acting on a set \(V\) are said to be intersecting if \(g(v) = h(v)\) for some \(v \in V\). More generally, a subset \(\mathcal{F}\) of \(G\) is an intersecting set if every pair of elements of \(\mathcal{F}\) is intersecting. The intersection density \(\rho (G)\) of a transitive permutation group \(G\) is the maximum value of the quotient \(|\mathcal{F}|/|G_v|\) where \(G_v\) is the stabilizer of \(v \in V\) and \(\mathcal{F}\) runs over all intersecting sets in \(G\). Intersection densities of transitive groups of degree \(pq\), where \(p > q\) are odd primes, is considered. In particular, the conjecture that the intersection density of every such group is equal to 1 (posed in [K. Meagher et al., J. Comb. Theory, Ser. A 180, Article ID 105390, 27 p. (2021; Zbl 1459.05122)]) is disproved by constructing a family of imprimitive permutation groups of degree \(pq\) (with blocks of size \(q)\), where \(p = (q^k -1) /(q-1)\), whose intersection density is equal to \(q\). The construction depends heavily on certain equidistant cyclic codes \([p,k]_q\) over the field \(\mathbb{F}_q\) whose codewords have Hamming weight strictly smaller than \(p\).

MSC:

20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

Citations:

Zbl 1459.05122

Software:

Magma
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bonisoli, A., Every equidistant linear code is a sequence of dual Hamming codes, Ars Comb., 18, 181-186 (1984) · Zbl 0561.94006
[2] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system I: the user language, J. Symb. Comput., 24, 235-265 (1997) · Zbl 0898.68039
[3] Clark, W. E., Equidistant cyclic codes over GF(q), Discrete Math., 17, 139-141 (1977) · Zbl 0356.94010
[4] Du, S. F.; Kutnar, K.; Marušič, D., Resolving the Hamiltonian problem for vertex-transitive graphs of order a product of two primes, Combinatorica, 41, 507-543 (2021) · Zbl 1499.05340
[5] Huffman, W. C.; Pless, V., Fundamentals of Error-Correcting Codes (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1099.94030
[6] Jones, G. A.; Zvonkin, A. K., Primes in geometric series and finite permutation groups (2020), preprint
[7] Jones, G. A.; Zvonkin, A. K., Groups of prime degree and the Bateman-Horn conjecture (2021), preprint
[8] Hujdurović, A.; Kutnar, K.; Marušič, D.; Miklavič, Š., Intersection density of transitive groups of certain degrees (2021), preprint
[9] Li, C. H.; Song, S. J.; Pantangi, V. R.T., Erdös-Ko-Rado problems for permutation groups (2020), preprint
[10] Lidl, R.; Niederreiter, H., Finite Fields, Encyclopedia of Mathematics and its Applications, vol. 20 (1997), Cambridge University Press: Cambridge University Press Cambridge, with a foreword by P.M. Cohn
[11] Marušič, D., On vertex symmetric digraphs, Discrete Math., 36, 69-81 (1981) · Zbl 0459.05041
[12] Marušič, D.; Scapellato, R., Characterizing vertex-transitive pq-graphs with an imprimitive subgroup of automorphisms, J. Graph Theory, 16, 375-387 (1992) · Zbl 0764.05035
[13] Marušič, D.; Scapellato, R., Classifying vertex-transitive graphs whose order is a product of two primes, Combinatorica, 14, 187-201 (1994) · Zbl 0799.05027
[14] McEliece, R. J., Irreducible cyclic codes and Gauss sums, (Combinatorics, Part 1: Theory of Designs, Finite Geometry and Coding Theory, Proc. NATO Advanced Study Inst.. Combinatorics, Part 1: Theory of Designs, Finite Geometry and Coding Theory, Proc. NATO Advanced Study Inst., Breukelen, 1974. Combinatorics, Part 1: Theory of Designs, Finite Geometry and Coding Theory, Proc. NATO Advanced Study Inst.. Combinatorics, Part 1: Theory of Designs, Finite Geometry and Coding Theory, Proc. NATO Advanced Study Inst., Breukelen, 1974, Math. Centre Tracts, vol. 55 (1974), Math. Centrum: Math. Centrum Amsterdam), 179-196 · Zbl 0309.94022
[15] Meagher, K.; Razafimahatratra, A. S.; Spiga, P., On triangles in derangement graphs, J. Comb. Theory, Ser. A, 180, Article 105390 pp. (2021) · Zbl 1459.05122
[16] Niederreiter, H., Weights of cyclic codes, Inf. Control, 34, 130-140 (1977) · Zbl 0357.94008
[17] Praeger, C. E.; Wang, R. J.; Xu, M. Y., Symmetric graphs of order a product of two distinct primes, J. Comb. Theory, Ser. B, 58, 299-318 (1993) · Zbl 0793.05071
[18] Praeger, C. E.; Xu, M. Y., Vertex primitive transitive graphs of order a product of two distinct primes, J. Comb. Theory, Ser. B, 59, 245-266 (1993) · Zbl 0793.05072
[19] Razafimahatratra, A. S., On multipartite derangement graphs, Ars Math. Contemp. (2021) · Zbl 1479.05147
[20] Wan, Z.-X., Finite Fields and Galois Rings (2012), World Scientific Publishing Co. Pte. Ltd.: World Scientific Publishing Co. Pte. Ltd. Hackensack, NJ · Zbl 1267.12001
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.