Abstract
dc:descriptionThe forbidden configuration problem arises from a question in extremal set theory. The question seeks a bound on the maximum number of subsets of an m-set 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 sub-hypergraph. 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 sub-hypergraph. F need not be simple. We define forb(m, F ) as the maximum number of columns possible for a simple, m-rowed, (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, m-rowed, (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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Mathematics
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2013
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Koch, Christina Louise
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/44225