A Caltech Library Service

Forbidden configurations and Steiner designs

Balachandran, Niranjan (2012) Forbidden configurations and Steiner designs. Designs, Codes and Cryptography, 65 (3). pp. 353-364. ISSN 0925-1022. doi:10.1007/s10623-012-9699-x.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
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”.
Subject Keywords:Forbidden configurations; Steiner designs; Nonuniform Ray–Chaudhuri–Wilson theorem
Issue or Number:3
Classification Code:Mathematics Subject Classification: 05B30; 05D05
Record Number:CaltechAUTHORS:20130204-114113579
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:36758
Deposited By: Jason Perez
Deposited On:04 Feb 2013 22:52
Last Modified:09 Nov 2021 23:24

Repository Staff Only: item control page