Richard Anstee

Most Recent Course Websites

Math 444 Section 202 (Jan, 2022)
Math 223 Section 101 (Sept, 2021)
Math 340 Section 201 (Jan, 2020)
Math 443 Section 201 (Jan, 2018)
Math 441 Section 101 (Sept, 2016)
Math 105 Section 203 (Jan, 2016)
Math 184 Section 201 (Jan, 2014)
Math 523 Section 201 (Jan , 2012)
Math 104 Section 103 (Sept, 2006)

Advice


Various bits of Information (advice) for undergraduates is at the bottom of this page. I may be able to help give general 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)
Farzad Fallahi (USRA 2015)
Santiago Salazar (USRA 2016)
Jeffrey Dawson (USRA 2017)
Cindy Tan (USRA 2018)
Zachary Pellegrin (USRA 2019)
Kim Dinh (supported NSERC RA 2020)
Niko Nikov (USRA 2021)
Arvin Sahami (USRA 2022)
Oakley Edens (USRA 2022)

Recent graduate students


Hangjun (Gavin) Yang MSc 2005
Miguel Raggi Ph.D. 2011 Thesis (August 2011)
Christina Koch MSc 2013 Thesis (April 2013)
Vedang Vyas MSc 2016 Thesis: On Methods of Induction in the study of Forbidden Configurations
Zoe Hamel MSc 2016 Thesis: Graph Decomposition based on Degree Constraints (April 2016)
Timothy Pressey MSc 2017 Thesis: Linear Algebra and Forbidden Configurations (August 2017)
Ethan White MSc Thesis: On Rigidity of Unit-Bar Frameworks (April 2019)
Ethan White PhD
Gabriel Currier MSc
Gabriel Currier PhD
Anshula Gandhi MSc

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 and Algebra.

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 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 great number of people: Robert (Tank) Aldred, Farzin Barekat, Jeffrey Dawson, Kim Dinh, Laura Dunwoody, Jerry Griggs, Martin Farber, Ron Ferguson, Balin Fleming, Zoltan Furedi, Nima Kamoosi, Steven Karp, Peter Keevash, Christina Koch, Linyuan (Lincoln) Lu, Connor Meehan, U.S.R. Murty, Niko Nikov, Zachary Pellegrin, Miguel Raggi, Lajos Ronyai, Chris Ryan, Santiago Salazar 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 polynomials. 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.


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



Forbidden Configurations: A shattered history Columbia College, Vancouver, December 7, 2015. (pdf file)

Design Theory and Extremal Combinatorics AMS meeting, Seattle, January 7, 2016. (pdf file)

Dominoes and Matchings UBC Math Circle, January 25, 2016. (pdf file)

Forbidden Configurations: Asymptotic Bounds Workshop on Extremal and Random Phenomenon in Discrete Mathematics, Tianjin, May 14, 2016. (pdf file)

Forbidden Berge Hypergraphs given by Santiago Salazar in the Discrete Mathematic Seminar UBC, October 4, 2016. (pdf file)

Induction handout given in Math Circle, Jan 16, 2017. (pdf file)

Forbidden Berge Hypergraphs Talk at CanaDAM 2017, Jun 12, 2017. (pdf file)

Forbidden Configurations Talk for Jerry GriggsÕ retirement. April 27, 2018 in Columbia South Carolina. (pdf file)

Dominoes and Matchings UBC Math Circle, February 3, 2020. (pdf file)

The quest of the perfect square UBC Math Circle, January 25, 2021. (pdf file)

Extensions to the complete object. Talk by Niko Nikov, UBC Discrete Mathematics Seminar, November 2, 2021. (pdf file)

SpernerÕs Theorem UBC Math Circle, February 14, 2022. (pdf file)

Forbidden configurations; A Shattered History UBC Undergraduate Math society, March 2, 2022. (pdf file)

Work in progress

Publications

Information for Undergraduates

Some links for pursuing teaching

A collection of advising documents

Web page prepared March 25, 2015 meeting for students who will be graduating next year, 2016. . Informal advice for graduating students such as letter writers/references, special exams, course selection, job experiences. Some discussion of careers. Some specialized information for those interested in Mathematics graduate school.

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

Web page for Math Information Session March 2011

Go to UBC Math. Home Page

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