Go to  Advanced Search

Forbidden configurations

Show simple item record

dc.contributor.author Raggi, Miguel
dc.date.accessioned 2011-08-09T17:05:00Z
dc.date.available 2011-08-09T17:05:00Z
dc.date.copyright 2011 en_US
dc.date.issued 2011-08-09
dc.identifier.uri http://hdl.handle.net/2429/36598
dc.description.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. en_US
dc.language.iso eng en_US
dc.publisher University of British Columbia en
dc.rights Attribution-NonCommercial 2.5 Canada *
dc.rights.uri http://creativecommons.org/licenses/by/3.0/ *
dc.title Forbidden configurations en_US
dc.type Electronic Thesis or Dissertation en
dc.degree.name Doctor of Philosophy - PhD en_US
dc.degree.discipline Mathematics en_US
dc.degree.grantor University of British Columbia en
dc.date.graduation 2011-11 en_US
dc.degree.campus UBCV en_US
dc.description.scholarlevel Graduate en


Files in this item

Files Size Format Description   View
ubc_2011_fall_raggi_miguel.pdf 912.3Kb Adobe Portable Document Format   View/Open
 

This item appears in the following Collection(s)

Show simple item record

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

Attribution-NonCommercial 2.5 Canada Except where otherwise noted, this item's license is described as Attribution-NonCommercial 2.5 Canada

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893