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: |
| |||||||||
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