 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Families of forbidden configurations
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Families of forbidden configurations Koch, Christina Louise
Abstract
The forbidden configuration problem arises from a question in extremal set theory. The question seeks a bound on the maximum number of subsets of an mset given that some trace is forbidden. In terms of hypergraphs, we seek the maximum number of edges on a simple hypergraph of m vertices such that this hypergraph does not contain a forbidden subhypergraph. We will use the notation of matrices to describe the problem as follows. We call a (0,1)matrix simple if it has no repeated columns; this will be the analogue of a simple hypergraph. Let F be a given matrix. We say that a (0,1)matrix A contains F as a configuration if there is some submatrix of A that is a row and column permutation of F. This is equivalent to a hypergraph containing some subhypergraph. F need not be simple. We define forb(m, F ) as the maximum number of columns possible for a simple, mrowed, (0,1)matrix that does not contain F as a configuration. A variation of the forbidden configuration problem forbids a family of configurations F = {F₁, F₂, ... Fn} instead of a single configuration F. Thus, forb(m, F) becomes the maximum number of columns possible for a simple, mrowed, (0,1)matrix that does not contain any one of the matrices in the family as a configuration. We will present a series of results organized by the character of forb(m, F). These include a classification of families such that forb(m, F) is a constant and the unexpected result that for a certain family, forb(m, F) is on the order of m³/², where previous results typically had forb(m, F) on the order of integer powers of m. We will conclude with a case study of families of forbidden configurations and suggestions for future work.
Item Metadata
Title 
Families of forbidden configurations

Creator  
Publisher 
University of British Columbia

Date Issued 
2013

Description 
The forbidden configuration problem arises from a question in extremal set theory. The question seeks a bound on the maximum number of subsets of an mset given that some trace is forbidden. In terms of hypergraphs, we seek the maximum number of edges on a simple hypergraph of m vertices such that this hypergraph does not contain a forbidden subhypergraph.
We will use the notation of matrices to describe the problem as follows. We call a (0,1)matrix simple if it has no repeated columns; this will be the analogue of a simple hypergraph. Let F be a given matrix. We say that a (0,1)matrix A contains F as a configuration if there is some submatrix of A that is a row and column permutation of F. This is equivalent to a hypergraph containing some subhypergraph. F need not be simple. We define forb(m, F ) as the maximum number of columns possible for a simple, mrowed, (0,1)matrix that does not contain F as a configuration.
A variation of the forbidden configuration problem forbids a family of configurations F = {F₁, F₂, ... Fn} instead of a single configuration F. Thus, forb(m, F) becomes the maximum number of columns possible for a simple, mrowed, (0,1)matrix that does not contain any one of the matrices in the family as a configuration.
We will present a series of results organized by the character of forb(m, F). These include a classification of families such that forb(m, F) is a constant and the unexpected result that for a certain family, forb(m, F) is on the order of m³/², where previous results typically had forb(m, F) on the order of integer powers of m. We will conclude with a case study of families of forbidden configurations and suggestions for future work.

Genre  
Type  
Language 
eng

Date Available 
20130417

Provider 
Vancouver : University of British Columbia Library

Rights 
AttributionNonCommercialNoDerivatives 4.0 International

DOI 
10.14288/1.0073659

URI  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Graduation Date 
201305

Campus  
Scholarly Level 
Graduate

Rights URI  
Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
AttributionNonCommercialNoDerivatives 4.0 International