Richard Anstee

Most Recent Course Websites (on sabbatical July 2012-June 2013)

Math 184 Section 201 (Jan, 2014)
Math 443 Section 101 (Sept, 2013)
Math 441 Section 201 (Sept, 2014)
Math 223 Section 102 (Sept, 2014)
Math 340 Section 202 (Jan, 2012)
Math 523 Section 201 (Jan , 2011)
Math 104 Section 103 (Sept, 2006)

Advice


Various bits of Information (advice) for undergraduates is at the bottom of this page. I am currently the advior for students in the Dual Degree program combining a B.Sc. with a B.Ed. In this role I am the person selecting eligible students (from the Mathematics side) and providing guidance during their time in the program. I may be able to help other students with other issues if you contact me.

Recent undergraduate research students


Tim Chan (USRA 2001)
Nima Kamoosi (USRA 2002)
Balin Fleming (USRA 2003)
Chris Ryan (USRA 2004)
Laura Dunwoody (USRA 2005)
Robert Tseng (USRA 2006)
Farzin Barekat (NSERC RA 2007)
Steven Karp (USRA 2008)
Jonathan Blackman (USRA 2009)
Connor Meehan (USRA 2010)
Ronnie Chen (USRA 2011)
Ron Estrin (USRA 2012)
Foster Tom (USRA 2013)
Maxwell Allman (USRA 2014)

Recent graduate students


Hangjun (Gavin) Yang MSc 2005
Miguel Raggi Ph.D. 2011 Thesis (August 2011)
Christina Koch MSc 2013 Thesis (April 2013)

Research Interests

Discrete Mathematics, Extremal Set Theory, Graph Theory, Matching Theory

Research in Progress

Discrete Mathematics has burgeoned as an area of research. Discrete Mathematics is characterized by the study of problems with a discrete rather than continuous structure. One seeks structural information of special combinatorial objects as well as studying their enumeration. Also one seeks efficient algorithms for finding optimal combinatorial objects. There is a stimulating interface with application areas in computer science and operations management that has provided motivation and problems for research. And increasingly there is a discrete mathematics component in other areas of Mathematics such as Probablility.

Matching theory is an important foundational topic in combinatorial optimization. An optimal degree constrained subgraph of a given graph is sought. The simplest case seeks to match vertices in pairs. I have obtained efficient strongly polynomial algorithms using the fact that fractional degree constrained subgraphs can easily be obtained via network flows. I have obtained some simplified existence theorems this way which have been useful in some graph decomposition problems of a design theory nature. I have recently explored (with Tank Aldred, Jonathan Blackman, Steve Locke, Robert Tseng, Gavin (Hangjun) Yang) the extent to which certain graphs are robust with respect to the property of having a perfect matching under vertex deletion. Of course not all vertex deletions are allowable such as the need to delete an even number of vertices, avoiding deleting all neighbours of a vertex and, if the graph is bipartite, deleting the same number of vertices from each part.

I have considered some extremal problems of the following type. Given a family of subsets of a set of size n where the family satisfies certain specified properties, determine the maximum possible number of subsets in the family as a function of n. For certain specified properties, exact best possible bounds have been obtained and sometimes the structure of families achieving the bounds are elucidated. In other cases asymptotically best possible bounds are obtained. The main current problem is establishing a conjecture on what properties of the forbidden configuration drive the asymptotics. This has been joint work with a number of people (Tank Aldred, Farzin Barekat, Laura Dunwoody, Jerry Griggs, Martin Farber, Ron Ferguson, Balin Fleming, Zoltan Furedi, Nima Kamoosi, Steven Karp, Peter Keevash, Christina Koch, Connor Meehan, U.S.R. Murty, Miguel Raggi, Lajos Ronyai, Chris Ryan, and Attila Sali). I have worked on Forbidden Submatrices, the ordered version of Forbidden Configurations with Ruiyuan (Ronnie) Chen, Ron Estrin and Zoltan Furedi. A great many combinatorial structures have forbidden substructures and the results above find application in other combinatorial problems.

Graph theory is a central area in combinatorics. A variety of problems are considered such as examining the structure of certain classes of graphs. With Martin Farber results were obtained concerning the class of bridged graphs. These are graphs which contain no cycle of length greater than three as an isometric subgraph. With J. Pryzytcki and D. Rolfsen, results of Tutte on rotors in graphs and chromatic polynomials were extended to mutations of knots and knot polynominals. Fast algorithms for determining diameter critical graphs using Fast Matrix multiplication were developed.

Forbidden Configurations

I have a dynamic survey article in the Electronic Journal of Combinatorics entitled "A Survey of Forbidden Configuration Results" that collects a number of published results together, highlights the conjecture of Sali and myself, and identifies some other open problems. This is a work in progress (hence "dynamic" survey) and any comments are welcomed. I'm sure I've left off interesting results of others. I will try to prepare an update in a year. A survey of Forbidden Configuration results (pdf file)


The following download of code written by Miguel Raggi FConfThesisVersion.tar.gz contains the Ph.D. thesis version of program that accepts as input an integer k and a configuration (or a set of configurations) and determines what is missing on k rows in a matrix avoiding the given configuration(s). This software has been helpful in proving a number of results but is not expected to work for k greater than 6.

Shattered Sets

The following Java applet was written by Nima Kamoosi (NSERC USRA summer 2002) to display the shattered sets associated with a set system. I have difficulty getting it to run on all systems; it was written with Java 2.

 

 applet



Various Old (Beamer) Talks. More recent talks below.



Forbidden Submatrices SIAM Discrete Mathematics Conference, Halifax, June 19, 2012. (pdf file)

Student Research U of South Carolina, February 26, 2013. (pdf file)

Critical Substructures SIAM SEAS, U of Tennessee, March 23, 2013. (pdf file)

Forbidden Families of Configurations AMS, U of Iowa, Ames IA, April 28, 2013. (pdf file)

Forbidden Families of Configurations St. John's Newfoundland, June 13, 2013. (pdf file)

Large Forbidden Configurations Minneapolis, June 17, 2014. (pdf file)

Forbidden Configurations: A shattered history Combinatorial Potlatch, University of Western Washington, 2014. (pdf file)

Work in progress

Publications

Information for Undergraduates

A collection of advising documents

Web page for Math Information Session March 2011

My informal advice for graduating students who are interested in graduate school.

Careers blurb; some ideas about the many directions students have pursued.

Go to UBC Math. Home Page

A blog with pictures from Keramic Studio magazine; a hobby of mine.