Top

Designs, Codes and Cryptography

Published in:

29-04-2023

Optimal and extremal graphical designs on regular graphs associated with classical parameters

Author: Yan Zhu

Published in: Designs, Codes and Cryptography | Issue 8/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Graphical designs are the extension of spherical designs to finite graphs from the viewpoint of quadrature formulas. In this paper, we investigate optimal graphical designs on hypercubes, especially the conjecture proposed by Babecki that the Hamming code is an optimal graphical design on the hypercube. We prove that this conjecture is not true using certain binary t-error-correcting BCH codes. We also obtain extremal graphical designs on the furthest distance graph of 13 families of distance-regular graphs with classical parameters. This generalizes the result that any 1-intersecting family achieving Erdös–Ko–Rado type bound is an extremal graphical design on the Kneser graph.

previous article A bivariate polynomial-based cryptographic hard problem and its applications

next article Differential spectrum of a class of APN power functions

Babecki C.: Codes, cubes, and graphical designs. J. Fourier Anal. Appl. 27(5), 1–34 (2021).MathSciNetCrossRefMATH

Bannai E., Ito T.: Algebraic Combinatorics I: Association Schemes. Benjamin/Cummings, Menlo Park, CA (1984).MATH

Bannai E., Bannai E., Ito T., Tanaka R.: Algebraic Combinatorics. De Gruyter Series in Discrete Mathematics and Applications 5, De Gruyter (2021).

Brouwer A.E., Cioabă S.M., Ihringer F., McGinnis M.: The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters. J. Combin. Theory Ser. B 133, 88–121 (2018).MathSciNetCrossRefMATH

Brouwer A.E., Cohen A.M., Neumaier A.: Distance-Regular Graphs. Springer, Berlin (1989).CrossRefMATH

Brouwer A.E., Godsil C.D., Koolen J.H., Martin W.J.: Width and dual width of subsets in polynomial association schemes. J. Combin. Theory Ser. A 102(2), 255–271 (2003).MathSciNetCrossRefMATH

Chihara L., Stanton D.: Association schemes and quadratic transformations for orthogonal polynomials. Graphs Combin. 2(1), 101–112 (1986).MathSciNetCrossRefMATH

Ciobua S.M., Gupta H.: On the eigenvalues of Grassmann graphs, Bilinear forms graphs and Hermitian forms graphs. Graphs Combin. 38, 30 (2022).MathSciNetCrossRef

Delsarte P.: An Algebraic Approach to the Association Schemes of Coding Theory. PhD thesis, Universite Catholique de Louvain (1973).

10.

Delsarte P.: Association schemes and \(t\)-designs in regular semilattices. J. Combin. Theory Ser. A 20(2), 230–243 (1976).MathSciNetCrossRefMATH

11.

Delsarte P., Goethals J.M., Seidel J.J.: Spherical codes and designs. Geom. Dedicata 6(3), 363–388 (1977).MathSciNetCrossRefMATH

12.

Erdös P., Ko C., Rado R.: Intersection theorems for systems of finite sets. Q. J. Math. 12, 313–320 (1961).MathSciNetCrossRefMATH

13.

Golubev K.: Graphical designs and extremal combinatorics. Linear Algebra Appl. 604, 490–506 (2020).MathSciNetCrossRefMATH

14.

Kasami T.: Weight distributions of Bose-Chaudhuri-Hocquenghem codes. Coordinated Science Laboratory Report no. R-317 (1966).

15.

Luz C.J.: A characterization of Delsarte’s linear programming bound as a ratio bound. Linear Algebra Appl. 423(1), 99–108 (2007).MathSciNetCrossRefMATH

16.

MacWilliams F.J., Sloane N.J.A.: The Theory of Error Correcting Codes. North Holland, Amsterdam (1977).MATH

17.

Sobolev S.L.: Cubature formulas on the sphere which are invariant under transformations of finite rotation groups. In: Doklady Akademii Nauk, Vol. 146, pp. 310–313. Russian Academy of Sciences (1962).

18.

Steinerberger S.: Generalized designs on graphs: sampling, spectra, symmetries. J. Graph Theory 93(2), 253–267 (2020).MathSciNetCrossRefMATH

19.

Tanaka H.: Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs. J. Combin. Theory Ser. A 113(5), 903–910 (2006).MathSciNetCrossRefMATH

20.

Tanaka H.: Vertex subsets with minimal width and dual width in \(Q\)-polynomial distance-regular graphs. Electron. J. Combin. 18(1), Paper 167, 32 (2011).

21.

Tanaka H.: The Erdös-Ko-Rado theorem for twisted Grassmann graphs. Combinatorica 32(6), 735–740 (2012).MathSciNetCrossRefMATH

Title: Optimal and extremal graphical designs on regular graphs associated with classical parameters
Author: Yan Zhu
Publication date: 29-04-2023
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 8/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01231-7

Springer Professional

Optimal and extremal graphical designs on regular graphs associated with classical parameters

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 8/2023

The q-ary Golay arrays of size are standard

Block-transitive 3-(v, k, 1) designs associated with alternating groups

Improving the minimum distance bound of Trace Goppa codes

A bivariate polynomial-based cryptographic hard problem and its applications

Two faces of blindness

More results on large sets of Kirkman triple systems

Premium Partner