Large sets with multiplicity

Designs, Codes and Cryptography - Large sets of combinatorial designs has always been a fascinating topic in design theory. These designs form a partition of the whole space into combinatorial...     

Optimal doubly constant weight codes

A doubly constant weight code is a binary code of length n₁ + n₂, with constant weight w₁ + w₂, such that the weight of a codeword in the first n₁ coordinates is w₁. Such codes have applications in obtaining bounds on the sizes of constant weight codes with given minimum distance. Lower and upper bounds on the sizes of such codes are derived. In particular, we show tight connections between optimal codes and some known designs such as Howell designs, Kirkman squares, orthogonal arrays, Steiner systems, and large sets of Steiner systems. These optimal codes are natural generalization of Steiner systems and they are also called doubly Steiner systems. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 137–151, 2008     

Optimal tristance anticodes in certain graphs

For z₁,z₂,z₃∈Zⁿ, the tristance d₃(z₁,z₂,z₃) is a generalization of the L₁-distance on Zⁿ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeA_d of diameter d is a subset of Zⁿ with the property that d₃(z₁,z₂,z₃)?d for all z₁,z₂,z₃∈A_d. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z² for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z² where d(z₁,z₂)=1 if z₁,z₂ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z² is replaced by the hexagonal lattice A₂. We also investigate optimal tristance anticodes in Z³ and optimal quadristance anticodes in Z², and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go.     

Intersection of Isomorphic Linear Codes

Given an (n, k) linear code over GF(q), the intersection of with a codeπ( ), whereπS_n, is an (n, k₁) code, where max{0, 2k−n}k₁k. The intersection problem is to determine which integers in this range are attainable for a given code . We show that, depending on the structure of the generator matrix of the code, some of the values in this range are attainable. As a consequence we give a complete solution to the intersection problem for most of the interesting linear codes, e.g. cyclic codes, Reed–Muller codes, and most MDS codes.     

Configuration distribution and designs of codes in the Johnson scheme

The main goal of this article is to present several connections between perfect codes in the Johnson scheme and designs, and provide new tools for proving Delsarte conjecture that there are no nontrivial perfect Codes in the Johnson scheme. Three topics will be considered. The first is the configuration distribution which is akin to the weight distribution in the Hamming scheme. We prove that if there exists an e‐perfect code in the Johnson scheme then there is a formula which connects the number of vectors at distance i from any codeword in various codes isomorphic to . The second topic is the Steiner systems embedded in a perfect code. We prove a lower bound on the number of Steiner systems embedded in a perfect code. The last topic is the strength of a perfect code. We show two new methods for computing the strength of a perfect code and demonstrate them on 1‐perfect codes. We further discuss how to settle Delsarte conjecture. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 15–34, 2007     

Covering of subspaces by subspaces

Lower and upper bounds on the size of a covering of subspaces in the Grassmann graph \(\mathcal{G }_q(n,r)\) by subspaces from the Grassmann graph \(\mathcal{G }_q(n,k)\) , \(k \ge r\) , are discussed. The problem is of interest from four points of view: coding theory, combinatorial designs, \(q\) -analogs, and projective geometry. In particular we examine coverings based on lifted maximum rank distance codes, combined with spreads and a recursive construction. New constructions are given for \(q=2\) with \(r=2\) or \(r=3\) . We discuss the density for some of these coverings. Tables for the best known coverings, for \(q=2\) and \(5 \le n \le 10\) , are presented. We present some questions concerning possible constructions of new coverings of smaller size.     

Bounds on the sizes of constant weight covering codes

Motivated by applications in universal data compression algorithms we study the problem of bounds on the sizes of constant weight covering codes. We are concerned with the minimal sizes of codes of lengthn and constant weightu such that every word of lengthn and weightv is within Hamming distanced from a codeword. In addition to a brief summary of part of the relevant literature, we also give new results on upper and lower bounds to these sizes. We pay particular attention to the asymptotic covering density of these codes. We include tables of the bounds on the sizes of these codes both for small values ofn and for the asymptotic behavior. A comparison with techniques for attaining bounds for packing codes is also given. Some new combinatorial questions are also arising from the techniques.Part of this work was done while the first and third authors were visiting Bellcore. The third author was supported in part by National Science Foundation under grant NCR-8905052. Part of this work was presented in the Coding and Quantization Workshop at Rutgers University, NJ, October 1992.     

Author index for volume 39

The distribution γ(c, n) of de Bruijn sequences of order n and linear complexity c is investigated. Some new results are proved on the distribution of de Bruijn sequences of low complexity, i.e., their complexity is between 2^n?1 + n and 2^n?1 + 2^n?2. It is proved that for n ? 5 and 2^n?1 + n?c<2^n?1 + 2^n?2, γ(c, n) ≡ 0 (mod 4). It is shown that for n ? 11, γ(2^n?1 + n, n) > 0. It is also proved that γ(2^n?1 + 2^n?2, n) ? 4γ(2^n?2 ? 1, n ? 2) and we give a recursive method to generate de Bruijn sequences of complexity 2^n?1 + 2^n?2.     

Large sets of coverings

Large sets of packings were investigated extensively. Much less is known about the dual problem, i.e., large sets of coverings. We examine two types of important questions in this context; what is the maximum number of disjoint optimal coverings? and what is the minimum number of optimal coverings for which the union covers the space? We give various constructions which give the optimal solutions and some good upper and lower bounds on both questions, respectively. © 1994 John Wiley & Sons, Inc.     

Symmetry‐Enthalpy Correlations in Diels–Alder Reactions

Woodward–Hoffmann (WH) rules provide strict symmetry selection rules: when they are obeyed, a reaction proceeds; when they are not obeyed, there is no reaction. However, the voluminous experimental literature provides ample evidence that strict compliance to symmetry requirements is not an obstacle for a concerted reaction to proceed, and therefore the idea has developed that it is enough to have a certain degree of the required symmetry to have reactivity. Here we provide quantitative evidence of that link, and show that as one deviates from the desired symmetry, the enthalpy of activation increases, that is, we show that concerted reactions slow down the further they are from the ideal symmetry. Specifically, we study the deviation from mirror symmetry (evaluated with the continuous symmetry measure (CSM)) of the [4+2] carbon skeleton of the transition state of a series of twelve Diels–Alder reactions in seven different solvents (and in the gas phase), in which the dienes are butadiene, cyclopentadiene, cyclohexadiene, and cycloheptadiene; the dienophiles are the 1‐, 1,1‐, and 1,1,2‐cyanoethylene derivatives; the solvents were chosen to sample a range of dielectric constants from heptane to ethanol. These components provide twenty‐four symmetry–enthalpy DFT‐calculated correlation lines (out of which only one case is a relatively mild exception) that show the general trend of increase in enthalpy as symmetry decreases. The various combinations between the dienophiles, cyanoethylenes, and solvents provide all kinds of sources for symmetry deviations; it is therefore remarkable that although the enthalpy of activation is dictated by various parameters, symmetry emerges as a primary parameter. In our analysis we also bisected this overall picture into solvent effects and geometry variation effects to evaluate under which conditions the electronic effects are more dominant than symmetry effects.