Go to
Advanced Search

- cIRcle Home
- Graduate Theses and Dissertations
- Electronic Theses and Dissertations (ETDs) 2008+
- View Item

Please note that cIRcle is currently being upgraded to DSpace v5.1. The upgrade means that the cIRcle service will not be accepting new material from 05:00 on September 1/15 until 08:00 on September 4/15. Read only access will be available during this period. Apologies for the inconvenience.

Files | Size | Format | Description | View | |
---|---|---|---|---|---|

ubc_2013_spring_koch_christina.pdf | 499.8Kb | Adobe Portable Document Format |
View/ |

Title: | Families of forbidden configurations |

Author: | Koch, Christina Louise |

Degree | Master of Science - MSc |

Program | Mathematics |

Copyright Date: | 2013 |

Publicly Available in cIRcle | 2013-04-17 |

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

URI: | http://hdl.handle.net/2429/44225 |

Scholarly Level: | Graduate |

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library | Hours | Site Map | Contact Us

UBC Library

1961 East Mall

Vancouver, B.C.

Canada V6T 1Z1

Tel: 604-822-6375

Fax: 604-822-3893