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     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

Improved Dynamic Text Indexing

In the dynamic text indexing problem, a text string has to be maintained under string insertions and deletions in order to answer on-line queries about arbitrary pattern occurrences. By means of some new techniques and data structures, we achieve improved worst-case bounds. We show that finding allpoccoccurrences of a pattern of lengthpin the current text of lengthntakesO(p + pocc + updlog p + log n) time, whereupdis the number of text uptakes performed so far; inserting or deleting a string of lengthsfrom the current text takesO(s log(s + n)) time.     

Linear Programming Bounds for Codes of Small Size

Combining linear programming with the Plotkin–Johnson argument for constant weight codes, we derive upper bounds on the size of codes of lengthnand minimum distanced=(n − j) /2, 0<j<n^1/3.Forj=o(n^1/3)these bounds practically coincide with (are slightly better than) the Tietäväinen bound. Forjfixed and forjproportional ton^1/3, j<n^1/3-(2 /9)ln n,it improves on the earlier known results.     

De Bruijn cycles for covering codes

A de Bruijn covering code is a q‐ary string S so that every q‐ary string is at most R symbol changes from some n‐word appearing consecutively in S. We introduce these codes and prove that they can have size close to the smallest possible covering code. The proof employs tools from field theory, probability, and linear algebra. Included is a table of the best known bounds on the lengths of small binary de Bruijn covering codes, up to R = 11 and n = 13, followed by several open questions in this area. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

The last packing number of quadruples,and cyclic SQS

The packing number of quadruples without common triples of ann-set, or the maximum number of codewords of a code of lengthn, constant weight 4, and minimum Hamming distance 4, is an old problem. The only unsolved case isn5 (mod 6). For 246 values of the formn5 (mod 6), we present constant weight codes with these parameters, of size [(n–1)(n ² –3n–4)]/24, which is greater by (4n-20/24) from the previous lower bound and leaves a gap of [(n–5)/12] to the known upper bound. For infinitely many valuesn5 (mod 6) we give enough evidence to believe that such codes exist. The constructed codes are optimal extended cyclic codes with these parameters. The construction of the code is done by a new approach of analyzing the Köhler orbit graph. We also use this analysis to construct new S-cyclic Steiner Quadruple Systems. Another important application of the analysis is in the design of optical orthogonal codes.This research was supported in part by the Technion V.P.R. Fund.     

On maximal Spherical codes II

We consider spherical codes attaining the Levenshtein upper bounds on the cardinality of codes with prescribed maximal inner product. We prove that the even Levenshtein bounds can be attained only by codes which are tight spherical designs. For every fixed n ≥ 5, there exist only a finite number of codes attaining the odd bounds. We derive different expressions for the distance distribution of a maximal code. As a by-product, we obtain a result about its inner products. We describe the parameters of those codes meeting the third Levenshtein bound, which have a regular simplex as a derived code. Finally, we discuss a connection between the maximal codes attaining the third bound and strongly regular graphs. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 316–326, 1999     

On Upper Bounds for Minimum Distance and Covering Radius of Non-binary Codes

We consider upper bounds on two fundamental parameters of a code; minimum distance and covering radius. New upper bounds on the covering radius of non-binary linear codes are derived by generalizing a method due to S. Litsyn and A. Tietäväinen lt:newu and combining it with a new upper bound on the asymptotic information rate of non-binary codes. The upper bound on the information rate is an application of a shortening method of a code and is an analogue of the Shannon-Gallager-Berlekamp straight line bound on error probability. These results improve on the best presently known asymptotic upper bounds on minimum distance and covering radius of non-binary codes in certain intervals.     

Constructions and bounds on linear error-block codes

We obtain new bounds on the parameters and we give new constructions of linear error-block codes. We obtain a Gilbert–Varshamov type construction. Using our bounds and constructions we obtain some infinite families of optimal linear error-block codes over . We also study the asymptotic of linear error-block codes. We define the real valued function α _q,m,a (δ), which is an analog of the important real valued function α _q (δ) in the asymptotic theory of classical linear error-correcting codes. We obtain both Gilbert–Varshamov and algebraic geometry type lower bounds on α _q,m,a (δ). We compare these lower bounds in graphs.      

Kernels of nonlinear Hamming codes

Given a binary code,C, of lengthn, thekernel of the code is defined to be the set of all vectors which leave the code invariant under translation. Throughout this paper, various properties of kernels will be considered. However, the main idea of this paper is to show the necessary and sufficient conditions for the existence of kernels of all possible sizes for nonlinear perfect binary codes.     

On designs and formally self-dual codes

Binary formally self-dual (f.s.d.) even codes are the one type of divisible [2n, n] codes which need not be self-dual. We examine such codes in this paper. On occasion a f.s.d. even [2n, n] code can have a larger minimum distance than a [2n, n] self-dual code. We give many examples of interesting f.s.d even codes. We also obtain a strengthening of the Assmus-Mattson theore. IfC is a f.s.d. extremal code of lengthn2 (mol 8) [n 6 (mod 8)], then the words of a fixed weight inC C hold a 3-design [1-design]. Finally, we show that the extremal f.s.d. codes of lengths 10 and 18 are unique.The author thanks the University of Illinois at Chicago for their hospitality while this work was in progress.This work was supported in part by NSA Grant MDA 904-91-H-0003.     

Some Upper Bounds on the Covering Radii of Linear Codes Over Fq and Their Applications

We show that the covering radius R of an [n,k,d] code over F_q is bounded above by R n-n _q(k, d/q). We strengthen this bound when R d and find conditions under which equality holds.As applications of this and other bounds, we show that all binary linear codes of lengths up to 15, or codimension up to 9, are normal. We also establish the normality of most codes of length 16 and many of codimension 10. These results have applications in the construction of codes that attain t[n,k,/it>], the smallest covering radius of any binary linear [n,k].We also prove some new results on the amalgamated direct sum (ADS) construction of Graham and Sloane. We find new conditions assuring normality of the ADS; covering radius 1 less than previously guaranteed for ADS of codes with even norms; good covering codes as ADS without the hypothesis of normality, from concepts p- stable and s- stable; codes with best known covering radii as ADS of two, often cyclic, codes (thus retaining structure so as to be suitable for practical applications).     

Bounds on the Generalised Acyclic Chromatic Numbers of Bounded Degree Graphs

We give upper bounds for the generalised acyclic chromatic number and generalised acyclic edge chromatic number of graphs with maximum degree d, as a function of d. We also produce examples of graphs where these bounds are of the correct order. Part of this work supported by an Australian Research Council Postdoctoral Fellowship     

Random walks on highly symmetric graphs

We consider uniform random walks on finite graphs withn nodes. When the hitting times are symmetric, the expected covering time is at least 1/2n logn-O(n log logn) uniformly over all such graphs. We also obtain bounds for the covering times in terms of the eigenvalues of the transition matrix of the Markov chain. For distance-regular graphs, a general lower bound of (n-1) logn is obtained. For hypercubes and binomial coefficient graphs, the limit law of the covering time is obtained as well.     

Polynomial systems with few real zeroes

We study some systems of polynomials whose support lies in the convex hull of a circuit, giving a sharp upper bound for their numbers of real solutions. This upper bound is non-trivial in that it is smaller than either the Kouchnirenko or the Khovanskii bounds for these systems. When the support is exactly a circuit whose affine span is ℤⁿ, this bound is 2n+1, while the Khovanskii bound is exponential in n². The bound 2n+1 can be attained only for non-degenerate circuits. Our methods involve a mixture of combinatorics, geometry, and arithmetic. Part of work done at MSRI was supported by NSF grant DMS-9810361. Work of Sottile is supported by the Clay Mathematical Institute. Sottile and Bihan were supported in part by NSF CAREER grant DMS-0134860. Bertrand is supported by the European research network IHP-RAAG contract HPRN-CT-2001-00271.     

Hyperplane codes

We construct a family of linear codes of lengthN=( _m ⁿ )(q-1) ^m-1 and of dimensionn (orn−1) overGF(q). Their minimum distance and their weight distribution are calculated. These codes are subschemes of the hypercubic association schemeH(N,q).     

Percolation on random recursive trees

We study Bernoulli bond percolation on a random recursive tree of size n with percolation parameter p(n) converging to 1 as n tends to infinity. The sizes of the percolation clusters are naturally stored in a tree structure. We prove convergence in distribution of this tree‐indexed process of cluster sizes to the genealogical tree of a continuous‐state branching process in discrete time. As a corollary we obtain the asymptotic sizes of the largest and next largest percolation clusters, extending thereby a recent work of Bertoin [5]. In a second part, we show that the same limit tree appears in the study of the tree components which emerge from a continuous‐time destruction of a random recursive tree. We comment on the connection to our first result on Bernoulli bond percolation. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 655–680, 2016     

Polynomial techniques for investigation of spherical designs

We investigate the structure of spherical τ-designs by applying polynomial techniques for investigation of some inner products of such designs. Our approach can be used for large variety of parameters (dimension, cardinality, strength). We obtain new upper bounds for the largest inner product, lower bounds for the smallest inner product and some other bounds. Applications are shown for proving nonexistence results either in small dimensions and in certain asymptotic process. In particular, we complete the classification of the cardinalities for which 3-designs on exist for n = 8, 13, 14 and 18. We also obtain new asymptotic lower bound on the minimum possible odd cardinality of 3-designs.      

Undetected error probability of q-ary constant weight codes

In this paper, we introduce a new combinatorial invariant called q-binomial moment for q-ary constant weight codes. We derive a lower bound on the q-binomial moments and introduce a new combinatorial structure called generalized (s, t)-designs which could achieve the lower bounds. Moreover, we employ the q-binomial moments to study the undetected error probability of q-ary constant weight codes. A lower bound on the undetected error probability for q-ary constant weight codes is obtained. This lower bound extends and unifies the related results of Abdel-Ghaffar for q-ary codes and Xia-Fu-Ling for binary constant weight codes. Finally, some q-ary constant weight codes which achieve the lower bounds are found.