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     

Large sets with holes

We study large sets of disjoint Steiner triple systems “with holes”. The purpose of these structures is to extend the use of large sets of disjoint Steiner triple systems in the construction of various other large set type structures to values of v for which no Steiner triple system of order v exists, i.e., v ≡ 0, 2, 4, or 5 (mod 6). We give constructions for all of these congruence classes. We describe several applications, including applications to large sets of disjoint group divisible designs and to large sets of disjoint separable ordered designs. © 1993 John Wiley & Sons, Inc.     

完美门限方案的组合构造

部分平衡t-设计t-(v; b;w; 1; 0) (X;A) 称为可划分的, 如果它同时也是一个部分平衡(t-1)-设计(t -1)-(v; b;w; λ_t-1; 0) 并且可将区组集A划分为A₁;…;A_λt-1; 使得每个(X;A_i) (1≤i≤λ_t-1)是一个部分平衡(t-1)-设计(t-1)-(v; b/λ_t-1;w; 1; 0). 本文证明可划分部分平衡t-设计PPBD t-(v; b;w;λ_t-1; 1; 0) 的存在性蕴含着完美(t;w; v;λ_t-1)-门限方案的存在性; 而且在某些情况下, 最优可划分部分平衡t-设计OPPBD(t;w; v) 的存在性等价于最优(t;w; v)-门限方案的存在性. 由此我们得到了最优(t;w; v)-门限方案的一些新的无穷类.     

Optimal Colored Threshold Visual Cryptography Schemes

Visual cryptography schemes allow the encoding of a secret image into n shares which are distributed to the participants. The shares are such that only qualified subsets of participants can visually recover the secret image. Usually the secret image consist of black and white pixels. In colored threshold visual cryptography schemes the secret image is composed of pixels taken from a given set of c colors. The pixels expansion and the contrast of a scheme are two measures of the goodness of the scheme.In this paper, we study c-color (k,n)-threshold visual cryptography schemes and provide a characterization of contrast-optimal schemes. More specifically we prove that there exists a contrast-optimal scheme that is a member of a special set of schemes, which we call canonical schemes, and that satisfy strong symmetry properties.Then we use canonical schemes to provide a constructive proof of optimality, with respect to the pixel expansion, of c-color (n,n)-threshold visual cryptography schemes.Finally, we provide constructions of c-color (2,n)-threshold schemes whose pixels expansion improves on previously proposed schemes.*This author is also a member of the Akamai Faculty Group, Akamai Technologies, 8 Cambridge center, Cambridge, MA 02142, USA.     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

Further results on large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ were first studied by Schellenberg and Stinson because of their connection with perfect threshold schemes. It is known that such large sets can exist only for n ≡0 (mod 3) and do exist for all odd n ≡ (mod 3) and for even n=24m, where m odd ≥ 1. In this paper, we show that such large sets exist also for n=2^k(3m), where m odd≥ 1 and k≥ 5. To accomplish this, we present two quadrupling constructions and two tripling constructions for a special large set called ^*LS(2ⁿ). © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 24–35, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10032     

Large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ have been studied by Schellenberg, Chen, Lindner and Stinson. These large sets have applications in cryptography in the construction of perfect threshold schemes. It is known that such large sets can exist only for n ≡ 0 (mod 3) and do exist for n = 6 and for all n = 3^k, k ≥ 1. In this paper, we present new recursive constructions and use them to show that such large sets exist for all odd n ≡ 0 (mod 3) and for even n = 24m, where m odd ≥ 1. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 285–296, 2001     

Hyperovals in Steiner systems

In this paper, we show that the basic necessary condition for the existence of a (k; 0, 2)-set in an S(2, 4, v) is also sufficient. It solves a problem posed by de Resmini [6] and we also prove some asymptotic results concerning the existence of hyperovals in Steiner systems with large block size. The results are generally applicable to designs with maximal arcs.     

Doubling and Tripling Constructions for Defining Sets in Steiner Triple Systems

 A minimal defining set of a Steiner triple system on v points (STS(v)) is a partial Steiner triple system contained in only this STS(v), and such that any of its proper subsets is contained in at least two distinct STS(v)s. We consider the standard doubling and tripling constructions for STS(2v+1) and STS(3v) from STS(v) and show how minimal defining sets of an STS(v) gives rise to minimal defining sets in the larger systems. We use this to construct some new families of defining sets. For example, for Steiner triple systems on 3 ⁿ points, we construct minimal defining sets of volumes varying by as much as 7 ⁿ⁻² . Received: September 16, 2000 Final version received: September 13, 2001 RID="*" ID="*" Research supported by the Australian Research Council A49937047, A49802044     

Improved Schemes for Visual Cryptography

A (k,n)-threshold visual cryptography scheme ((k,n)-threshold VCS, for short) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the visual recovery of the secret image, but by inspecting less than k shares one cannot gain any information on the secret image. The visual recovery consists of xeroxing the shares onto transparencies, and then stacking them. Any k shares will reveal the secret image without any cryptographic computation.In this paper we analyze visual cryptography schemes in which the reconstruction of black pixels is perfect, that is, all the subpixels associated to a black pixel are black. For any value of k and n, where 2 k n, we give a construction for (k,n)-threshold VCS which improves on the best previously known constructions with respect to the pixel expansion (i.e., the number of subpixels each pixel of the original image is encoded into). We also provide a construction for coloured (2,n)-threshold VCS and for coloured (n,n)-threshold VCS. Both constructions improve on the best previously known constructions with respect to the pixel expansion.     

Steiner triple systems with two disjoint subsystems

It is shown that there exists a triangle decomposition of the graph obtained from the complete graph of order v by removing the edges of two vertex disjoint complete subgraphs of orders u and w if and only if u,w, and v are odd, (mod 3), and . Such decompositions are equivalent to group divisible designs with block size 3, one group of size u, one group of size w, and v – u – w groups of size 1. This result settles the existence problem for Steiner triple systems having two disjoint specified subsystems, thereby generalizing the well‐known theorem of Doyen and Wilson on the existence of Steiner triple systems with a single specified subsystem. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Embedding partial steiner triple systems is NP-complete

It is known that any partial Steiner triple system of order υ can be embedded in a Steiner triple system of order w whenever w?4υ+1, and w≡1, 3 (mod 6); moreover, it is conjectured that the same is true whenever w?2υ+1. By way of contrast, it is proved that deciding whether a partial Steiner triple system of order υ can be embedded in a Steiner triple system of order w for any w?2υ?1 is NP-complete. In so doing, it is proved that deciding whether a partial commutative quasigroup can be completed to a commutative quasigroup is NP-complete.     

On the Lipschitz equivalence of self‐affine sets

Recently Lipschitz equivalence of self‐similar sets on has been studied extensively in the literature. However for self‐affine sets the problem is more awkward and there are very few results. In this paper, we introduce a w‐Lipschitz equivalence by repacing the Euclidean norm with a pseudo‐norm w. Under the open set condition, we prove that any two totally disconnected integral self‐affine sets with a common matrix are w‐Lipschitz equivalent if and only if their digit sets have equal cardinality. The main methods used are the technique of pseudo‐norm and Gromov hyperbolic graph theory on iterated function systems.     

Secret sharing schemes with partial broadcast channels

In a conventional secret sharing scheme a dealer uses secure point-to-point channels to distribute the shares of a secret to a number of participants. At a later stage an authorised group of participants send their shares through secure point-to-point channels to a combiner who will reconstruct the secret. In this paper, we assume no point-to-point channel exists and communication is only through partial broadcast channels. A partial broadcast channel is a point-to-multipoint channel that enables a sender to send the same message simultaneously and privately to a fixed subset of receivers. We study secret sharing schemes with partial broadcast channels, called partial broadcast secret sharing schemes. We show that a necessary and sufficient condition for the partial broadcast channel allocation of a (t, n)-threshold partial secret sharing scheme is equivalent to a combinatorial object called a cover-free family. We use this property to construct a (t, n)-threshold partial broadcast secret sharing scheme with O(log n) partial broadcast channels. This is a significant reduction compared to n point-to-point channels required in a conventional secret sharing scheme. Next, we consider communication rate of a partial broadcast secret sharing scheme defined as the ratio of the secret size to the total size of messages sent by the dealer. We show that the communication rate of a partial broadcast secret sharing scheme can approach 1/O(log n) which is a significant increase over the corresponding value, 1/n, in the conventional secret sharing schemes. We derive a lower bound on the communication rate and show that for a (t,n)-threshold partial broadcast secret sharing scheme the rate is at least 1/t and then we propose constructions with high communication rates. We also present the case of partial broadcast secret sharing schemes for general access structures, discuss possible extensions of this work and propose a number of open problems.      

Doyen–Wilson theorem for nested Steiner triple systems

The obvious necessary conditions for the existence of a nested Steiner triple system of order v containing a nested subsystem of order w are v ≥ 3w + 4 and v ≡ w ≡ 1 (mod 6). We show that these conditions are also sufficient. © 2004 Wiley Periodicals, Inc.     

On the Steiner quadruple systems of small rank which are embeddable into extended perfect binary codes

The codewords of weight 4 of every extended perfect binary code that contains the all-zero vector are known to form a Steiner quadruple system. We propose a modification of the Lindner construction for the Steiner quadruple system of order N = 2 ^r which can be described by special switchings from the Hamming Steiner quadruple system. We prove that each of these Steiner quadruple systems is embedded into some extended perfect binary code constructed by the method of switching of ijkl-components from the binary extended Hamming code. We give the lower bound for the number of different Steiner quadruple systems of order N with rank at most N ? logN + 1 which are embedded into extended perfect codes of length N.     

Existence of good large sets of Steiner triple systems

The concept of good large set of Steiner triple systems (or GLS in short) was introduced by Lu in his paper “on large sets of disjoint Steiner triple systems”, [J. Lu, On large sets of disjoint Steiner triple systems, I-III, J. Combin. Theory (A) 34 (1983) 140-182]. In this paper a doubling construction for GLSs is displayed and some existence results are obtained.     

A construction of mutually disjoint Steiner systems from isomorphic Golay codes

It is well known that the extended binary Golay [24,12,8] code yields 5-designs. In particular, the supports of all the weight 8 codewords in the code form a Steiner system S(5,8,24). In this paper, we give a construction of mutually disjoint Steiner systems S(5,8,24) by constructing isomorphic Golay codes. As a consequence, we show that there exists at least 22 mutually disjoint Steiner systems S(5,8,24). Finally, we prove that there exists at least 46 mutually disjoint 5-(48,12,8) designs from the extended binary quadratic residue [48,24,12] code.     

Existence of Generalized Steiner Systems <Emphasis Type="Italic">GS</Emphasis>(2,4,ν,2)

Generalized Steiner systems GS(2,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 five, in which each codeword has length v and weight four. Etzion conjectured its existence for any integer v 7 and v 1(mod 3). The conjecture has been verified for prime powers v > 7 and v 7(mod 12) by the latter two of the present authors. It has also been pointed out that there does not exist a GS(2,4,7,2). In this paper, constructions using frame generalized Steiner systems, two holey perfect bases and orthogonal Latin squares are discussed. With these constructions the conjecture is confirmed with the exception for v=7 and three possible exceptions for v 13, 52, 58.AMS classification: 05B05, 94B25     

On cliques in spanning graphs of projective Steiner triple systems

We are interested in the sizes of cliques that are to be found in any arbitrary spanning graph of a Steiner triple system 𝒮. In this paper we investigate spanning graphs of projective Steiner triple systems, proving, not surprisingly, that for any positive integer k and any sufficiently large projective Steiner triple system 𝒮, every spanning graph of 𝒮 contains a clique of size k. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 157–165, 2000