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
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
dc.language.iso eng en
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
dc.type Electronic Thesis or Dissertation en
dc.degree.name Doctor of Philosophy - PhD en
dc.degree.discipline Mathematics en
dc.degree.grantor University of British Columbia en
dc.date.graduation 2011-11 en
dc.degree.campus UBCV en
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