CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20130204-114113579

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

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20130204-114113579

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/s10623-012-9699-xDOIUNSPECIFIED
http://link.springer.com/article/10.1007%2Fs10623-012-9699-xPublisherUNSPECIFIED
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
DOI:10.1007/s10623-012-9699-x
Record Number:CaltechAUTHORS:20130204-114113579
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20130204-114113579
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:36758
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:04 Feb 2013 22:52
Last Modified:09 Nov 2021 23:24

Repository Staff Only: item control page