Back to search

University of British Columbia

Families of forbidden configurations

Abstract

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

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Koch, Christina Louise. Families of forbidden configurations. master's thesis, University of British Columbia, 2013. http://hdl.handle.net/2429/44225