Quasi-symmetric designs on $ 56 $ points

Vedran Krčadinac; Renata Vlahović Kruc

doi:10.3934/amc.2020086

Article Contents

2021, Volume 15, Issue 4: 633-646. Doi: 10.3934/amc.2020086

This issue Previous Article An overview on skew constacyclic codes and their subclass of LCD codes Next Article Correlation distribution of a sequence family generalizing some sequences of Trachtenberg

Quasi-symmetric designs on $ 56 $ points

Vedran Krčadinac^, and
Renata Vlahović Kruc

Department of Mathematics, Faculty of Science, University of Zagreb, Bijenička 30, HR-10000 Zagreb, Croatia

^* Corresponding author: V. Krčadinac
^* Corresponding author: V. Krčadinac

Received: October 31, 2019

Revised: January 31, 2020

Early access: June 2020

Published: November 2021

This work has been fully supported by the Croatian Science Foundation under the project 6732

Abstract Full Text(HTML) Figure(2) / Table(5) Related Papers Cited by

Abstract

Computational techniques for the construction of quasi-symmetric block designs are explored and applied to the case with $ 56 $ points. One new $ (56,16,18) $ and many new $ (56,16,6) $ designs are discovered, and non-existence of $ (56,12,9) $ and $ (56,20,19) $ designs with certain automorphism groups is proved. The number of known symmetric $ (78,22,6) $ designs is also significantly increased.

Keywords:

Mathematics Subject Classification: 05B05, 94B25, 05C69.

Citation:

Full Text(HTML)

Figure 1.

Download: Full-size image PowerPoint slide

Figure 2.

Download: Full-size image PowerPoint slide

Table 1. The known QSDs with $ v = 56 $

No.	$ v $	$ k $	$ \lambda $	$ r $	$ b $	$ x $	$ y $	NQSD	Ref.
47	56	16	18	66	231	4	8	$ \ge 3 $	[13]
48	56	15	42	165	616	3	6	0	[5]
49	56	12	9	45	210	0	3	?
50	56	21	24	66	176	6	9	0	[5]
51	56	20	19	55	154	5	8	?
52	56	16	6	22	77	4	6	$ \ge 2 $	[24,16]

| Show Table

DownLoad: CSV

Table 3. Dimensions and weight distributions of self-orthogonal binary codes spanned by $ (56,16,6) $ QSDs

	$ \dim $	$ a_0 $	$ a_8 $	$ a_{12} $	$ a_{16} $	$ a_{20} $	$ a_{24} $	$ a_{28} $
$ C_1 $	26	1	91	2 016	152 425	2 939 776	16 194 619	28 531 008
$ C_2 $	26	1	7	$ 2\,016 $	$ 155\,365 $	$ 2\,926\,336 $	$ 16\,224\,019 $	$ 28\,493\,376 $
$ C_3 $	24	1	75	0	40 089	730 368	4 055 835	7 124 480
$ C_{4\hbox{-}6,9,10} $	22	1	15	0	9 933	183 168	1 012 515	1 783 040
$ C_{7,11\hbox{-}13} $	25	1	75	672	77 721	1 465 984	8 103 963	14 257 600
$ C_8 $	25	1	75	960	75 417	1 474 048	8 087 835	14 277 760
$ C_{14} $	22	1	15	0	10 701	178 560	1 024 035	1 767 680
$ C_{15} $	23	1	15	288	19 917	361 216	2 040 867	3 544 000
$ C_{16} $	23	1	15	96	19 917	365 056	2 028 579	3 561 280
$ C_{17} $	24	1	75	160	39 833	728 704	4 062 235	7 115 200
$ C_{18} $	22	1	15	64	9 677	183 424	1 012 771	1 782 400
$ C_{19,21,24} $	22	1	15	16	10 061	182 080	1 015 459	1 779 040
$ C_{20,22} $	22	1	15	64	10 445	178 816	1 024 291	1 767 040
$ C_{23} $	25	1	75	1 280	74 905	1 470 720	8 100 635	14 259 200
$ C_{25} $	25	1	75	992	77 209	1 462 656	8 116 763	14 239 040
$ C_{26} $	27	1	139	4 992	307 161	5 848 832	32 477 083	56 941 312
$ C_{27} $	27	1	99	4 304	305 873	5 872 320	32 406 731	57 039 072
$ C_{28,29} $	27	1	99	4 112	307 409	5 866 944	32 417 483	57 025 632
$ C_{30} $	26	1	147	1 008	158 529	2 920 512	16 231 467	28 485 536
$ C_{31,32,34,35} $	27	1	147	3 696	309 057	5 862 976	32 423 979	57 018 016
$ C_{33,39} $	27	1	147	4 976	307 009	5 849 664	32 475 179	56 943 776
$ C_{36} $	26	1	75	2 240	153 241	2 931 200	16 218 395	28 498 560
$ C_{37,38} $	27	1	75	4 416	305 817	5 871 616	32 408 859	57 036 160

| Show Table

DownLoad: CSV

Table 2. Dimensions and weight distributions of self-orthogonal binary codes spanned by $ (56,16,18) $ QSDs

	$ \dim $	$ a_0 $	$ a_8 $	$ a_{12} $	$ a_{16} $	$ a_{20} $	$ a_{24} $	$ a_{28} $
$ C_{1,2} $	23	1	75	0	21 657	353 536	2 059 035	3 520 000
$ C_3 $	19	1	0	0	1 722	19 936	134 085	212 800
$ C_4 $	23	1	15	216	20 493	359 200	2 044 899	3 538 960

| Show Table

DownLoad: CSV

Table 4. Distribution of the known $ (56,16,6) $ QSDs and symmetric $ (78,22,6) $ designs by full automorphism group order

$ \| \mathrm{Aut}\| $	#$ (56,16,6) $	#$ (78,22,6) $
$ 168 $	$ 1 $	$ 2 $
$ 78 $	$ 0 $	$ 1 $
$ 48 $	$ 876 $	$ 1664 $
$ 24 $	$ 1 $	$ 378 $
$ 21 $	$ 1 $	$ 2 $
$ 16 $	$ 228 $	$ 456 $
$ 12 $	$ 303 $	$ 606 $
$ 6 $	$ 0 $	$ 32 $

| Show Table

DownLoad: CSV

Table 5. An updated table of QSDs with $ v = 56 $

No.	$ v $	$ k $	$ \lambda $	$ r $	$ b $	$ x $	$ y $	NQSD
47	56	16	18	66	231	4	8	$ \ge 4 $
48	56	15	42	165	616	3	6	0
49	56	12	9	45	210	0	3	?
50	56	21	24	66	176	6	9	0
51	56	20	19	55	154	5	8	?
52	56	16	6	22	77	4	6	$ \ge 1410 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	T. Beth, D. Jungnickel and H. Lenz, Hanfried Design Theory. Vol. II, 2ⁿd edition, Cambridge University Press, Cambridge, 1999.
[2]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system Ⅰ: The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.
[3]	A. E. Brouwer, The uniqueness of the strongly regular graph on 77 points, J. Graph Theory, 7 (1983), 455-461. doi: 10.1002/jgt.3190070411.
[4]	A. E. Brouwer, Uniqueness and nonexistence of some graphs related to $M_22$, Graphs Combin., 2 (1986), 21-29. doi: 10.1007/BF01788073.
[5]	A. R. Calderbank, Geometric invariants for quasisymmetric designs, J. Combin. Theory Ser. A, 47 (1988), 101-110. doi: 10.1016/0097-3165(88)90044-1.
[6]	D. Crnković, D. Dumičić Danilović and S. Rukavina, On symmetric (78, 22, 6) designs and related self-orthogonal codes, Util. Math., 109 (2018), 227-253.
[7]	D. Crnković, B. G. Rodrigues, S. Rukavina and V. D. Tonchev, Quasi-symmetric $2$-$(64, 24, 46)$ designs derived from $AG(3, 4)$, Discrete Math., 340 (2017), 2472-2478. doi: 10.1016/j.disc.2017.06.008.
[8]	Y. Ding, S. Houghten, C. Lam, S. Smith, L. Thiel and V. D. Tonchev, Quasi-symmetric $2$-$(28, 12, 11)$ designs with an automorphism of order $7$, J. Combin. Des., 6 (1998), 213-223.
[9]	I. A. Faradžev, Constructive enumeration of combinatorial objects, in Problemes combinatoires et théorie des graphes, Colloq. Internat. CNRS, Paris, 1978,131–135.
[10]	The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.8.10, 2018., http://www.gap-system.org
[11]	Z. Janko and T. Van Trung, Construction of a new symmetric block design for $(78, 22, 6)$ with the help of tactical decompositions, J. Combin. Theory Ser. A, 40 (1985), 451-455. doi: 10.1016/0097-3165(85)90107-4.
[12]	V. Krčadinac, Steiner $2$-designs $S(2, 4, 28)$ with nontrivial automorphisms, Glas. Mat. Ser. III, 37(57) (2002), 259-268.
[13]	V. Krčadinac and R. Vlahović, New quasi-symmetric designs by the Kramer-Mesner method, Discrete Math., 339 (2016), 2884-2890. doi: 10.1016/j.disc.2016.05.030.
[14]	B. D. McKay, Isomorph-free exhaustive generation, J. Algorithms, 26 (1998), 306-324. doi: 10.1006/jagm.1997.0898.
[15]	B. D. McKay and A. Piperno, Practical graph isomorphism, Ⅱ, J. Symbolic Comput., 60 (2014), 94-112. doi: 10.1016/j.jsc.2013.09.003.
[16]	A. Munemasa and V. D. Tonchev, A new quasi-symmetric $2$-$(56, 16, 6)$ design obtained from codes, Discrete Math., 284 (2004), 231-234. doi: 10.1016/j.disc.2003.11.036.
[17]	A. Neumaier, Regular sets and quasisymmetric 2-designs, in Combinatorial Theory (Schloss Rauischholzhausen, 1982), Lecture Notes in Math., Vol. 969, Springer, Berlin-New York, 1982,258–275.
[18]	S. Niskanen and P. R. J. Östergård, Cliquer User's Guide, Version 1.0, Communications Laboratory, Helsinki University of Technology, Espoo, Finland, Tech. Rep. T48, 2003.
[19]	P. R. J. Östergård, A fast algorithm for the maximum clique problem, Discrete Appl. Math., 120 (2002), 197-207. doi: 10.1016/S0166-218X(01)00290-6.
[20]	R. M. Pawale, M. S. Shrikhande and S. M. Nyayate, Conditions for the parameters of the block graph of quasi-symmetric designs, Electron. J. Combin., 22 (2015), Paper 1.36, 30 pp. doi: 10.37236/3954.
[21]	R. C. Read, Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, in Ann. Discrete Math., 2, 1978,107–120. doi: 10.1016/S0167-5060(08)70325-X.
[22]	M. S. Shrikhande, Quasi-symmetric designs, in The CNC Handbook of Combinatorial Designs, Second Edition, CRC Press, Boca Raton, FL, 2007,578–582.
[23]	M. S. Shrikhande and S. S. Sane, Quasi-symmetric Designs, Cambridge University Press, Cambridge, 1991. doi: 10.1017/CBO9780511665615.
[24]	V. D. Tonchev, Embedding of the Witt-Mathieu system $S(3, 6, 22)$ in a symmetric $2$-$(78, 22, 6)$ design, Geom. Dedicata, 22 (1987), 49-75. doi: 10.1007/BF00183053.