Combinatorial design 

Also known as Block design, Covering design.

Description

A constant-weight binary code that is mapped into a combinatorial \(t\)-design.

The mapping proceeds as follows for a length-\(n\) code with codewords of constant weight \(w\). A codeword \(c\) corresponds to a block of the design, with the codeword's \(j\)th coordinate labeling whether or not element \(j\) is contained in the block. There are a total of \(n\) elements, and the constant weight of the code implies that each block contains a fixed number \(w\) of elements. The code supports an \(S(t,w,n)\) Steiner system if each subset of \(t\leq w\) elements is contained in exactly one block. More generally, the code supports a combinatorial \(t\)-design, or, more precisely, a \(t\)-\((n,w,\lambda)\)-design, if each such \(t\)-subset is contained in exactly \(\lambda \geq 1\) blocks. A combinatorial \(2\)-design with two block intersection sizes is called a quasi-symmetric design. A \(3\)-\((q^d+1,q+1,1)\) combinatorial design is sometimes called a Witt design (a.k.a. a spherical geometry design) [1,3][2; Remark 6.10].

For example, the eight codewords of weight \(w=3\) of the \([7,4,3]\) Hamming code support a \(2\)-\((7,3,1)\)-design a.k.a. an \(S(2,3,7)\) Steiner system. The codeword \(1000110\) corresponds to a block containing elements 1, 5, and 6. Similarly, the other seven codewords correspond to blocks 257, 367, 147, 246, 345, and 123. Each pair of elements is contained in exactly one block.

Combinatorial \(t\)-designs exist for all \(t\) [48]. Existence of certain quasi-symmetric designs has also been established [9].

Notes

See [1012] for reviews on combinatorial designs.See [2,1315] for books on combinatorial designs.

Parents

Cousins

References

[1]
E. Witt, “Über Steinersche Systeme”, Collected Papers - Gesammelte Abhandlungen 288 (1998) DOI
[2]
T. Beth, D. Jungnickel, and H. Lenz, Design Theory (Cambridge University Press, 1999) DOI
[3]
J. D. Key and A. Wagner, “On an infinite class of Steiner systems constructed from affine spaces”, Archiv der Mathematik 47, 376 (1986) DOI
[4]
P. Keevash, “The existence of designs”, (2019) arXiv:1401.3665
[5]
L. Teirlinck, “Non-trivial t-designs without repeated blocks exist for all t”, Discrete Mathematics 65, 301 (1987) DOI
[6]
S. Glock et al., “The existence of designs via iterative absorption: hypergraph \(F\)-designs for arbitrary \(F\)”, (2020) arXiv:1611.06827
[7]
P. Keevash, “The existence of designs II”, (2018) arXiv:1802.05900
[8]
P. Keevash, “A short proof of the existence of designs”, (2024) arXiv:2411.18291
[9]
G. McGuire, “Quasi-Symmetric Designs and Codes Meeting the Grey–Rankin Bound”, Journal of Combinatorial Theory, Series A 78, 280 (1997) DOI
[10]
W. de Launey and D. Flannery, Algebraic Design Theory (American Mathematical Society, 2011) DOI
[11]
V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[12]
M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Selected Topics in Information and Coding Theory 121 (2010) arXiv:0811.1254 DOI
[13]
C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
[14]
P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and Their Links (Cambridge University Press, 1991) DOI
[15]
Combinatorial Designs (Springer-Verlag, 2004) DOI
[16]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[17]
Delsarte, Philippe. "An algebraic approach to the association schemes of coding theory." Philips Res. Rep. Suppl. 10 (1973): vi+-97.
[18]
V. I. Levenshtein, “Universal bounds for codes and designs,” in Handbook of Coding Theory 1, eds. V. S. Pless and W. C. Huffman. Amsterdam: Elsevier, 1998, pp.499-648.
[19]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[20]
E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
[21]
E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
[22]
V. Pless, “The Weight of the Symmetry Code for p=29 and the 5‐Designs Contained Therein”, Annals of the New York Academy of Sciences 175, 310 (1970) DOI
[23]
V. Pless, “Symmetry codes over GF(3) and new five-designs”, Journal of Combinatorial Theory, Series A 12, 119 (1972) DOI
[24]
L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
[25]
K. T. Phelps, “Combinatorial designs and perfect codes”, Electronic Notes in Discrete Mathematics 10, 220 (2001) DOI
[26]
A. R. Calderbank, P. IDelsarte, and N. J. A. Sloane, “A strengthening of the Assmus-Mattson theorem”, IEEE Transactions on Information Theory 37, 1261 (1991) DOI
[27]
C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI
[28]
D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications”, Codes, Systems, and Graphical Models 113 (2001) DOI
[29]
S. J. Johnson and S. R. Weller, “Regular low-density parity-check codes from combinatorial designs”, Proceedings 2001 IEEE Information Theory Workshop (Cat. No.01EX494) DOI
[30]
S. J. Johnson and S. R. Weller, “Construction of low-density parity-check codes from Kirkman triple systems”, GLOBECOM’01. IEEE Global Telecommunications Conference (Cat. No.01CH37270) DOI
[31]
S. J. Johnson and S. R. Weller, “Resolvable 2-designs for regular low-density parity-check codes”, IEEE Transactions on Communications 51, 1413 (2003) DOI
[32]
J. A. Todd, “A Combinatorial Problem”, Journal of Mathematics and Physics 12, 321 (1933) DOI
[33]
C. Ding and C. Tang, “Infinite families of near MDS codes holding \(t\)-designs”, (2019) arXiv:1910.08265
[34]
C. Tang and C. Ding, “An infinite family of linear codes supporting 4-designs”, (2020) arXiv:2001.00158
[35]
M. Harada, A. Munemasa, and V. D. Tonchev, “A Characterization of Designs Related to an Extremal Doubly-Even Self-Dual Code of Length 48”, Annals of Combinatorics 9, 189 (2005) DOI
[36]
V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
[37]
W. J. Martin, Designs, Codes and Cryptography 16, 271 (1999) DOI
[38]
P. A. H. Bours, “On the construction of perfect deletion-correcting codes using design theory”, Designs, Codes and Cryptography 6, 5 (1995) DOI
[39]
A. Mahmoodi, Designs, Codes and Cryptography 14, 81 (1998) DOI
[40]
J. Kim and V. Pless, Designs, Codes and Cryptography 30, 187 (2003) DOI
[41]
C. Ding, C. Tang, and V. D. Tonchev, “The Projective General Linear Group \(\mathrm{PGL}_2(\mathrm{GF}(2^m))\) and Linear Codes of Length \(2^m+1\)”, (2020) arXiv:2010.09448
[42]
J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
[43]
D. Goyeneche et al., “Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices”, Physical Review A 92, (2015) arXiv:1506.08857 DOI
[44]
Y. Fujiwara et al., “Entanglement-assisted quantum low-density parity-check codes”, Physical Review A 82, (2010) arXiv:1008.4747 DOI
[45]
G. Alber et al., “Detected-jump-error-correcting quantum codes, quantum error designs, and quantum computation”, Physical Review A 68, (2003) arXiv:quant-ph/0208140 DOI
[46]
T. Beth et al., Designs, Codes and Cryptography 29, 51 (2003) DOI
[47]
Y. Lin and M. Jimbo, “Extremal properties of t-SEEDs and recursive constructions”, Designs, Codes and Cryptography 73, 805 (2013) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: combinatorial_design

Cite as:
“Combinatorial design”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/combinatorial_design
BibTeX:
@incollection{eczoo_combinatorial_design, title={Combinatorial design}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/combinatorial_design} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/combinatorial_design

Cite as:

“Combinatorial design”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/combinatorial_design

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/combinatorial_design.yml.