Forbidden configurations and repeated induction

For a given k×? matrix F, we say a matrix A has no configurationF if no k×? submatrix of A is a row and column permutation of F. We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. We define as the maximum number of columns in an m-rowed simple matrix which has no configuration F. A fundamental result of Sauer, Perles and Shelah, and Vapnik and Chervonenkis determines exactly, where K_k denotes the k×2^k simple matrix. We extend this in several ways. For two matrices G,H on the same number of rows, let [G∣H] denote the concatenation of G and H. Our first two sets of results are exact bounds that find some matrices B,C where and . Our final result provides asymptotic boundary cases; namely matrices F for which is O(m^p) yet for any choice of column α not in F, we have is Ω(m^p+1). This is evidence for a conjecture of Anstee and Sali. The proof techniques in this paper are dominated by repeated use of the standard induction employed in forbidden configurations. Analysis of base cases tends to dominate the arguments. For a k-rowed (0,1)-matrix F, we also consider a function which is the minimum number of columns in an m-rowed simple matrix for which each k-set of rows contains F as a configuration.     

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     

Forbidden configurations and subframe varieties

In a series of papers, Ball, Pultr, and Sichler studied forbidden configurations in Priestley spaces and Esakia spaces. They showed, among other things, that the class of Heyting algebras whose Esakia spaces contain no copy of a given finite configuration is a variety iff the configuration is a tree. In this short note, we show that such varieties are examples of subframe varieties—the algebraic counterparts of subframe logics introduced by Fine in the 1980s.     

Ubiquitous configurations in Steiner triple systems

A Steiner triple system S is a C-ubiquitous (where C is a configuration) if every line of S is contained in a copy of C, and is n-ubiquitous if it is C-ubiquitous for every n-line configuration C. We determine the spectrum of 4-ubiquitous Steiner triple systems as well as the spectra of C-ubiquitous Steiner triple systems for all configurations C with five lines. © 1997 John Wiley & Sons, Inc.     

Forbidden configurations for distributive and modular ordered sets

As modular and distributive ordered sets generalize modular and distributive lattices, it is a natural question to ask whether there exist some forbidden configurations for those ordered sets. We present such configurations in the form of strong subsets and LU subsets.     

Doubly resolvable Steiner quadruple systems and related designs

Two resolutions of the same \(\hbox {SQS}(v)\) are said to be orthogonal, when each parallel class of one resolution has at most one block in common with each parallel class of the other resolution. If an \(\hbox {SQS}(v)\) has two orthogonal resolutions, the \(\hbox {SQS}(v)\) is called a doubly resolvable \(\hbox {SQS}(v)\). In this paper, we use a quadrupling construction to obtain an infinite class of doubly resolvable Steiner quadruple systems. We also give some results of doubly resolvable H designs and doubly resolvable candelabra quadruple systems.     

Some rigid Steiner 5‐designs

Hitherto, all known non‐trivial Steiner systems S(5, k, v) have, as a group of automorphisms, either PSL(2, v−1) or PGL(2, (v−2)/2) × C₂. In this article, systems S(5, 6, 72), S(5, 6, 84) and S(5, 6, 108) are constructed that have only the trivial automorphism group. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:392–400, 2010     

On Steiner 3-wise balanced designs of order 17

We determine all S(3, κ, 17)'s which either; (i) have a block of size at least 6; or (ii) have an automorphism group order divisible by 17, 5, or 3; or (iii) contain a semi-biplane; or (iv) come from an S(3, κ, 16) which is not an S(3, 4, 16). There is an S(3, κ, 17) with |G| = n if and only if n ϵ {2^a3^b: 0 ≤ a ≤ 7,0 ≤ b ≤ 1} ∪ {18, 60, 144, 288, 320, 1920, 5760, 16320}. We also search the S(3, κ, 17)'s listed in the appendix for subdesigns S(2, κ, 17) and generate 22 nonisomorphic S(3, κ, 18)'s by adding a new point to such a subdesign. © 1997 John Wiley & Sons, Inc.     

Super‐simple holey Steiner pentagon systems and related designs

A Steiner pentagon system of order v (SPS(v)) is said to be super‐simple if its underlying (v, 5, 2)‐BIBD is super‐simple; that is, any two blocks of the BIBD intersect in at most two points. It is well known that the existence of a holey Steiner pentagon system (HSPS) of type T implies the existence of a (5, 2)‐GDD of type T. We shall call an HSPS of type T super‐simple if its underlying (5, 2)‐GDD of type T is super‐simple; that is, any two blocks of the GDD intersect in at most two points. The existence of HSPSs of uniform type hⁿ has previously been investigated by the authors and others. In this article, we focus our attention on the existence of super‐simple HSPSs of uniform type hⁿ. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 301–328, 2008     

A construction of 2-designs from Steiner systems and extendable designs

We give a construction of a 2-(mn²+1,mn,(n+1)(mn−1)) design starting from a Steiner system S(2,m+1,mn²+1) and an affine plane of order n. This construction is applied to known classes of Steiner systems arising from affine and projective geometries, Denniston designs, and unitals. We also consider the extendability of these designs to 3-designs.     

Product constructions for cyclic block designs II. Steiner 2-designs

Let CS(2, k, υ) denote a cyclic Steiner 2-design of order υ with block size k. Our main result is a product construction for obtaining a CS(2, q, uυ) from a CS(2, q, u) and a CS(2, q, υ) when q is a prime power and at least one of the latter two systems is composed entirely of full orbits.     

Euclidean designs obtained from spherical embedding of coherent configurations

Coherent configurations are a generalization of association schemes. Motivated by the recent study of Q-polynomial coherent configurations, in this paper, we study the spherical embedding of a Q-polynomial coherent configuration into some eigenspace by a primitive idempotent. We present a necessary and sufficient condition when the embedding becomes a Euclidean $t$-design (on two concentric spheres) in terms of the Krein numbers for $t\le 4$. In addition, we obtain some Euclidean 2- or 3-designs from spherical embedding of coherent configurations including tight relative 4- or 5-designs in binary Hamming schemes and the union of derived designs of a tight 4-design in Hamming schemes.     

Nilpotent block designs I: Basic concepts for Steiner triple and quadruple systems

This paper discusses the concepts of nilpotence and the center for Steiner Triple and Quadruple Systems. The discussion is couched in the language of block designs rather than algebras. Nilpotence is closely connected to the well known doubling and tripling constructions for these designs. A sample result: a point p in an STS is projective if every triangle containing p generates the 7-element Fano plane; the p-center of the STS is the set of all projective points and is a projective geometry over GF(2). © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 157–171, 1999     

A class of Steiner 4-wise balanced designs derived from preparata codes

The minimum weight codewords in the Preparata code of length n = 4^m are utilized for the construction of an infinite family of Steiner S(4, {5, 6}, 4^m + 1) designs for any m ≥ 2. © 1996 John Wiley & Sons, Inc.     

Product constructions for cyclic block designs. I. Steiner quadruple systems

Let CSQS(ν) denote a cyclic Steiner quadruple system of order ν. Various product constructions for CSQS(uν) are given. Amongst other results we show how to construct a CSQS(uν) (ν ? 0 (mod 4)) from a CSQS(u), a CSQS(2u) and a CSQS(ν).     

Constructions for cyclic 3‐designs and improved results on cyclic Steiner quadruple systems

This paper gives some recursive constructions for cyclic 3‐designs. Using these constructions we improve Grannell and Griggs's construction for cyclic Steiner quadruple systems, and many known recursive constructions for cyclic Steiner quadruple systems are unified. Finally, some new infinite families of cyclic Steiner quadruple systems are obtained. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:178‐201, 2011     

Linear spaces and transversal designs: k-anonymous combinatorial configurations for anonymous database search notes

Anonymous database search protocols allow users to query a database anonymously. This can be achieved by letting the users form a peer-to-peer community and post queries on behalf of each other. In this article we discuss an application of combinatorial configurations (also known as regular and uniform partial linear spaces) to a protocol for anonymous database search, as defining the key-distribution within the user community that implements the protocol. The degree of anonymity that can be provided by the protocol is determined by properties of the neighborhoods and the closed neighborhoods of the points in the combinatorial configuration that is used. Combinatorial configurations with unique neighborhoods or unique closed neighborhoods are described and we show how to attack the protocol if such configurations are used. We apply k-anonymity arguments and present the combinatorial configurations with k-anonymous neighborhoods and with k-anonymous closed neighborhoods. The transversal designs and the linear spaces are presented as optimal configurations among the configurations with k-anonymous neighborhoods and k-anonymous closed neighborhoods, respectively.