Constant Weight Codes and Group Divisible Designs

The study of a class of optimal constant weight codes over arbitrary alphabets was initiated by Etzion, who showed that such codes are equivalent to special GDDs known as generalized Steiner systems GS(t,k,n,g) Etzion. This paper presents new constructions for these systems in the case t=2, k=3. In particular, these constructions imply that the obvious necessary conditions on the length n of the code for the existence of an optimal weight 3, distance 3 code over an alphabet of arbitrary size are asymptotically sufficient.     

A census of highly symmetric combinatorial designs

As a consequence of the classification of the finite simple groups, it has been possible in recent years to characterize Steiner t-designs, that is t-(v,k,1) designs, mainly for t=2, admitting groups of automorphisms with sufficiently strong symmetry properties. However, despite the finite simple group classification, for Steiner t-designs with t>2 most of these characterizations have remained long-standing challenging problems. Especially, the determination of all flag-transitive Steiner t-designs with 3≤t≤6 is of particular interest and has been open for about 40 years (cf. Delandtsheer (Geom. Dedicata 41, p. 147, 1992 and Handbook of Incidence Geometry, Elsevier Science, Amsterdam, 1995, p. 273), but presumably dating back to 1965). The present paper continues the author’s work (see Huber (J. Comb. Theory Ser. A 94, 180–190, 2001; Adv. Geom. 5, 195–221, 2005; J. Algebr. Comb., 2007, to appear)) of classifying all flag-transitive Steiner 3-designs and 4-designs. We give a complete classification of all flag-transitive Steiner 5-designs and prove furthermore that there are no non-trivial flag-transitive Steiner 6-designs. Both results rely on the classification of the finite 3-homogeneous permutation groups. Moreover, we survey some of the most general results on highly symmetric Steiner t-designs.      

Generalized Steiner systems GS4 (2, 4, v,g) for g = 2, 3, 6

Generalized Steiner systems GS_d(t, k, v, g) were first introduced by Etzion and used to construct optimal constant‐weight codes over an alphabet of size g + 1 with minimum Hamming distance d, in which each codeword has length v and weight k. Much work has been done for the existence of generalized Steiner triple systems GS(2, 3, v, g). However, for block size four there is not much known on GS_d(2, 4, v, g). In this paper, the necessary conditions for the existence of a GS_d(t, k, v, g) are given, which answers an open problem of Etzion. Some singular indirect product constructions for GS_d(2, k, v, g) are also presented. By using both recursive and direct constructions, it is proved that the necessary conditions for the existence of a GS₄(2, 4, v, g) are also sufficient for g = 2, 3, 6. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 401–423, 2001     

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     

Note on large sets of infinite steiner systems

Large sets of Steiner systems S(t,k,n) exist for all finite t and k with t < k and all infinite n. The vector space analogues exist over a field F for all finite t and k with t < k provided that either v or F is infinite, and n ? 2k ? t + 1. This inequality is best possible. © 1995 John Wiley & Sons, Inc.     

On solvability and regularity of a parametrized version of optimality conditions

We investigate a linear homotopyF(·,t) connecting an appropriate smooth equationG=0 with Kojima's (nonsmooth) systemK=0 describing critical points (primal —dual) of a nonlinear optimization problem (NLP) in finite dimension.Fort=0, our system may be seen e.g. as a starting system for an embedding procedure to determine a critical point to NLP. Fort1, it may be regarded as a regularization ofK.Conditions for regularity (necessary and sufficient) and solvability (sufficient) are studied. Though, formally, they can be given in a unified way, we show that their meaning differs fort < 1 andt=1. Particularily, no MFCQ-like condition must be imposed in order to ensure regularity fort < 1.     

On a More General Characterisation of Steiner Systems

We introduce [k,d]-sparse geometries of cardinality n, which are natural generalizations of partial Steiner systems PS(t,k;n), with d=2(k−t+1). We will verify whether Steiner systems are characterised in the following way. (*) Let be a [k,2(k−t+1)]-sparse geometry of cardinality n, with k \> t \> 1$$" align="middle" border="0"> . If , then Γ is a S(t,k;n). If (*) holds for fixed parameters t, k and n, then we say S(t,k;n) satisfies, or has, characterisation (*). We could not prove (*) in general, but we prove the Theorems 1, 2, 3 and 4, which state conditions under which (*) is satisfied. Moreover, we verify characterisation (*) for every Steiner system appearing in list of the sporadic Steiner systems of small cardinality, and the list of infinite series of Steiner systems, both mentioned in the latest edition of the book ‘Design Theory’ by T. Beth, D. Jungnickel and H. Lenz. As an interesting application, one can use these results to build (almost) maximal binary codes in the following way. Every [k,d]-sparse geometry is associated with a [k,d]-sparse binary code of the same size (let and link every block with the code word where c_i=1 if and only if the point p_i is a member of B), so one can construct maximal [k,d]-sparse binary codes using (partial) Steiner systems. These [k,d]-sparse codes can then be used as building bricks for binary codes having a bigger variety of weights (the weight of a code word is the sum of its entries).     

The classification of flag-transitive Steiner 4-designs

Among the properties of homogeneity of incidence structures flag-transitivity obviously is a particularly important and natural one. Consequently, in the last decades flag-transitive Steinert-designs (i.e. flag-transitive t-(v,k,1) designs) have been investigated, whereas only by the use of the classification of the finite simple groups has it been possible in recent years to essentially characterize all flag-transitive Steiner 2-designs. However, despite the finite simple group classification, for Steiner t-designs with parameters t > 2 such characterizations have remained challenging open problems for about 40 years (cf. [11, p. 147] and [12 p. 273], but presumably dating back to around 1965). The object of the present paper is to give a complete classification of all flag-transitive Steiner 4-designs. Our result relies on the classification of the finite doubly transitive permutation groups and is a continuation of the author's work [20, 21] on the classification of all flag-transitive Steiner 3-designs. 2000 Mathematics Subject Classification. Primary 51E10 . Secondary 05B05 . 20B25     

On threshold schemes from large sets

An anonymous (t, w)-threshold scheme is one of the schemes for secret sharing. Combinatorial designs and especially large sets of Steiner systems and of Steiner systems “with holes” have an important role in the design of perfect (t, w)-threshold schemes. In this article we investigate perfect (4, 4)-threshold schemes. We use large sets to form such systems with a large number of keys. In particular we construct the first known infinite families of large sets of H-designs with block size 4. © 1996 John Wiley & Sons, Inc.     

More-Than-Nearly-Perfect Packings and Partial Designs

o (n) of the n vertices. Here we show, in particular, that regular uniform hypergraphs for which the ratio of degree to maximum codegree is , for some ɛ>0, have packings which cover all but vertices, where α=α(ɛ)>0. The proof is based on the analysis of a generalized version of R?dl's nibble technique. We apply the result to the problem of finding partial Steiner systems with almost enough blocks to be Steiner systems, where we prove that, for fixed positive integers t<k, there exist partial S(t,k,n)'s with at most uncovered t-sets, improving the earlier result. Received: September 23, 1994/Revised: November 14, 1996     

On the extendability of steiner t-designs

Necessary and sufficient conditions for the extendability of residual designs of Steiner systems S(t,t + 1,v) are studied. In particular, it is shown that a residual design with respect to a single point is uniquely extendable, and the extendability of a residual design with respect to a pair of points is equivalent to a bipartition of the block graph of a related design. © 1993 John Wiley & Sons, Inc.     

Perfect difference families,perfect difference matrices,and related combinatorial structures

The existence problems of perfect difference families with block size k, k=4,5, and additive sequences of permutations of length n, n=3,4, are two outstanding open problems in combinatorial design theory for more than 30 years. In this article, we mainly investigate perfect difference families with block size k=4 and additive sequences of permutations of length n=3. The necessary condition for the existence of a perfect difference family with block size 4 and order v, or briefly (v, 4,1)‐PDF, is v≡1(mod12), and that of an additive sequence of permutations of length 3 and order m, or briefly ASP (3, m), is m≡1(mod2). So far, (12t+1,4,1)‐PDFs with t<50 are known only for t=1,4−36,41,46 with two definiteexceptions of t=2,3, and ASP (3, m)'s with odd 3<m<200 are known only for m=5,7,13−29,35,45,49,65,75,85,91,95,105,115,119,121,125,133,135,145,147,161,169,175,189,195 with two definite exceptions of m=9,11. In this article, we show that a (12t+1,4,1)‐PDF exists for any t⩽1,000 except for t=2,3, and an ASP (3, m) exists for any odd 3<m<200 except for m=9,11 and possibly for m=59. The main idea of this article is to use perfect difference families and additive sequences of permutations with “holes”. We first introduce the concepts of an incomplete perfect difference matrix with a regular hole and a perfect difference packing with a regular difference leave, respectively. We show that an additive sequence of permutations is in fact equivalent to a perfect difference matrix, then describe an important recursive construction for perfect difference matrices via perfect difference packings with a regular difference leave. Plenty of perfect difference packings with a desirable difference leave are constructed directly. We also provide a general recursive construction for perfect difference packings, and as its applications, we obtain extensive recursive constructions for perfect difference families, some via incomplete perfect difference matrices with a regular hole. Examples of perfect difference packings directly constructed are used as ingredients in these recursive constructions to produce vast numbers of perfect difference families with block size 4. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 415–449, 2010     

Constructions for generalized Steiner systems <Emphasis Type="Italic">GS</Emphasis>(3, 4, <Emphasis Type="Italic">v</Emphasis>, 2)

Generalized Steiner systems GS (3, 4, v, 2) were first discussed by Etzion and used to construct optimal constant weight codes over an alphabet of size three with minimum Hamming distance three, in which each codeword has length v and weight four. Not much is known for GS (3, 4, v, 2)s except for a recursive construction and two small designs for v = 8,10 given by Etzion. In this paper, more small designs are found by computer search and also given are direct constructions based on finite fields and rotational Steiner quadruple systems and recursive constructions using three-wise balanced designs. Some infinite families are also obtained.      

A two-sample procedure for selecting the population with the largest mean fromk normal populations

Summary A two-sample procedure is given for selecting the population with the largest mean fromk normal populations with known variances. Thek populations are screened through the first sample for possible elimination of those populations which have considerably smaller means. The second sample is drawn from the non-eliminated populations only. The two-sample procedure is compared with the fixed sample procedure of Bechhofer [2]. The ratio of the expected total number of observations required in the first case to the total number of observations required in the second case for the same level of the probability of a correct selection measures the relative advantage of experimenting in two stages. Fork=2 it is shown that the ratio is bounded below by 1/4. Fork=2 the probability of a correct selection can be computed from the tables of the bivariate normal distribution function. Fork≧3 a lower bound on the probability of a correct selection is derived which can be computed with the help of available tables. An upper bound is also given for the expected sample size. The author's work was partly supported by the National Science Foundation Grant No. GP-7496 at Indiana University.     

The sharp Jackson inequality in the spaceL p on the sphere

The sharp Jackson inequality in the spaceL _p, 1≤p<2, on the unit Euclidean sphereS ⁿ⁻¹ ,n≥3, is proved. Forn=2, it was established by N. I. Chernykh. Translated fromMatematicheskie Zametki, Vol. 66, No. 1, pp. 50–62, July, 1999.     

Multidimensional cosmological solutions of Friedmann type

The generalization of cosmological models of Friedmann type (thet=const section is a manifold of constant curvature) to the case of an arbitrary numbern of spatial dimensions with allowance for the term is considered. Solutions are obtained in the integrable cases, in particular, for the distinguished valuen=2. Forn4 it is shown that the qualitative picture of the evolution is close to the ordinary scenario withn=3.State University, Tver. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 101, No. 3, pp. 458–466, December, 1994.     

Extendable Steiner designs

Let D be a Steiner t-design, where t2, with a collection C of subdesigns such that each member of C is a Steiner t-design whose blocks are blocks of D, and with the property that any (t+1) points of D are together in the point set of a unique member of C. It is shown that if every member of C can be extended to a (t+1)-design, then D can also be extended.The construction described is a development of ideas originally formulated in Assmus and Key [2].Dedicated to Professor A. Wagner on the occasion of his 60th birthday     

Influence of anti-diagonals on the asymptotic stability for linear differential systems

Sufficient conditions are given for asymptotic stability of the linear differential system x′  =  B(t)x with B(t) being a 2  ×  2 matrix. All components of B(t) are not assumed to be positive. The matrix B(t) is naturally divisible into a diagonal matrix D(t) and an anti-diagonal matrix A(t). Our concern is to clarify a positive effect of the anti-diagonal part A(t)x on the asymptotic stability for the system x′  =  B(t)x.      

Influence of anti-diagonals on the asymptotic stability for linear differential systems

Sufficient conditions are given for asymptotic stability of the linear differential system x′  =  B(t)x with B(t) being a 2  ×  2 matrix. All components of B(t) are not assumed to be positive. The matrix B(t) is naturally divisible into a diagonal matrix D(t) and an anti-diagonal matrix A(t). Our concern is to clarify a positive effect of the anti-diagonal part A(t)x on the asymptotic stability for the system x′  =  B(t)x.     

A construction for large sets of disjoint Kirkman triple systems

A Steiner system S(t, k, v) is called i-resolvable, 0 < i < t, if its block set can be partitioned into S(i, k, v). In this paper, a 2-resolvable S(3, 4, v) is used to construct a large set of disjoint Kirkman triple systems of order 3v − 3 (briefly LKTS) and some new orders for LKTS are then obtained. Research supported by Tianyuan Mathematics Foundation of NSFC Grant 10526032 and Natural Science Foundation of Universities of Jiangsu Province Grant 05KJB110111.