- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Forbidden configurations
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Forbidden configurations Raggi, Miguel
Abstract
In this work we explore the field of Forbidden Configurations, a problem in Extremal Set Theory. We consider a family of subsets of {1,2,...,m} as the corresponding {0,1}-incidence matrix. For {0,1}-matrices F, A, we say F is a *subconfiguration* of A if A has a submatrix which is a row and column permutation of F. We say a {0,1}-matrix is *simple* if it has no repeated columns. Let ||A|| denote the number of columns of A. A {0,1}-matrix F with row and column order stripped is a *configuration*. Given m and a family of configurations G, our main function of study is forb(m,G) := max{||A|| : A simple and for all F in G, we have F not a subconfiguration of A }. We give a general introduction to the main ideas and previous work done in the topic. We develop a new more computational approach that allows us to tackle larger problems. Then we present an array of new results, many of which were solved in part thanks to the new computational approach.
Item Metadata
Title |
Forbidden configurations
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2011
|
Description |
In this work we explore the field of Forbidden Configurations, a problem in Extremal Set Theory. We consider a family of subsets of {1,2,...,m} as the corresponding {0,1}-incidence matrix. For {0,1}-matrices F, A, we say F is a *subconfiguration* of A if A has a submatrix which is a row and column permutation of F. We say a {0,1}-matrix is *simple* if it has no repeated columns. Let ||A|| denote the number of columns of A. A {0,1}-matrix F with row and column order stripped is a *configuration*. Given m and a family of configurations G, our main function of study is forb(m,G) := max{||A|| : A simple and for all F in G, we have F not a subconfiguration of A }. We give a general introduction to the main ideas and previous work done in the topic. We develop a new more computational approach that allows us to tackle larger problems. Then we present an array of new results, many of which were solved in part thanks to the new computational approach.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2011-08-09
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution 3.0 Unported
|
DOI |
10.14288/1.0072028
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2011-11
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution 3.0 Unported