Richard Anstee

Professor

Relevant Degree Programs

 

Graduate Student Supervision

Doctoral Student Supervision (Jan 2008 - May 2019)
Forbidden configurations (2011)

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.

View record

Master's Student Supervision (2010 - 2018)
Families of forbidden configurations (2013)

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.

View record

 

Membership Status

Member of G+PS
View explanation of statuses

Program Affiliations

 

If this is your researcher profile you can log in to the Faculty & Staff portal to update your details and provide recruitment preferences.