Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2012 | public
Journal Article

Forbidden configurations and Steiner designs

Abstract

Let F be a (0, 1) matrix. A (0, 1) matrix M is said to have F as a configuration if there is a submatrix of M which is a row and column permutation of F . We say that a matrix M is simple if it has no repeated columns. For a given v∈N , we shall denote by forb (v,F) the maximum number of columns in a simple (0, 1) matrix with v rows for which F does not occur as a configuration. We say that a matrix M is maximal for F if M has forb (v,F) columns. In this paper we show that for certain natural choices of F , forb (v,F)≤(v_t)/(t+1). In particular this gives an extremal characterization for Steiner t-designs as maximal (0, 1) matrices in terms of certain forbidden configurations.

Additional Information

© 2012 Springer Science+Business Media, LLC. Received: 4 October 2010; Revised: 11 April 2011; Accepted: 12 May 2012; Published online: 30 June 2012. I would like to thank the anonymous referee for a patient reading, spotting several typographic errors and other inaccuracies, and for suggestions for improving the readability of the paper. This is one of several papers published together in Designs, Codes and Cryptography on the special topic: "Combinatorics – A Special Issue Dedicated to the 65th Birthday of Richard Wilson".

Additional details

Created:
August 22, 2023
Modified:
October 23, 2023