- Professor,
- Member of UBC Vancouver Senate, Joint Faculties, 2008-2017
- Background:
- B.Math., Waterloo (1976)
- Ph.D., Caltech (1980)
- NSERC PDF, Waterloo (1980-1982)
- NSERC URF, Waterloo (1982-1984)
- Office Location: Mathematics Annex, 1114
- Office Telephone: (604) 822-6105
- Email Address: anstee at math dot ubc dot ca
- Department Telephone: (604) 822-2666;

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)

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.

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)

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

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

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

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.

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)

- R.P. Anstee, N.A. Nikov, Extensions to the Complete Object. (arKiv 1409.4123) submitted to
*Elec. J. of Combinatorics*, 16pp, Oct, 2021 - R.P. Anstee, Linyuan Lu, Multicoloured Families of Forbidden Configurations. (arKiv 1409.4123) submitted to J. Comb. Th. Ser A., 16pp Sep 29, 2014 (pdf file)
- R.P. Anstee, F. Barekat, Design Theory and Some Non-simple Forbidden Configurations, (arKiv 1909.07580), 27pp. (pdf file)
- R.P. Anstee, J. Madden, Finding d-critical spanning subgraphs, preprint, 10pp.
- R.P. Anstee, Some problems concerning forbidden configurations, preprint, 10pp. (pdf file)
- R.P. Anstee, Yunsun Nam, Included and Excluded edges for regular factors.

- R.P. Anstee, Jeffrey Dawson, Linyuan Lu, Atilla Sali, Multivalued Matrices and Forbidden Configurations, 21pp, Discrete Math, to appear.
- R.P. Anstee, N.A. Nikov, Extensions to the Complete Object. (arKiv 1409.4123)
*Elec. J. of Combinatorics*, issue 2, P2.42, 10pp - R.P. Anstee, F. Barekat, Zachary Pellegrin, Design Theory and Some Forbidden Configurations (arXiv 1909.11602), Journal of Combinatorial Designs, . (pdf file)
- R.P. Anstee, Santiago Salazar, Forbidden Berge Hypergraphs,
*Elec. J. of Combinatorics*, (2017), 22pp. (arKiv 1608.03632) (pdf file) - R.P. Anstee, A. Sali, Large Forbidden Configurations and Design Theory, Studia. Sci. Math. Hung., 53(2016), 157-166. (pdf file)
- R.P. Anstee, Linyuan Lu, Repeated columns and an old chestnut,
*Elec. J. of Combinatorics*, 20(2013), issue 4, P2, 11pp (pdf file) (arXiv 1305.0603) - R.P. Anstee, C.L. Koch, Forbidden Families of Configurations,
*Australasian J. of Combinatorics*, 59(2014). 18pp (pdf file) (arXiv 1307.1148) - R.P. Anstee, C. Koch, M. Raggi, A, Sali, Forbidden Configurations and Product Constructions,
*Graphs and Combinatorics*, 30(2014), issue 6, 1325-1349. (pdf file) - R.P. Anstee, M. Raggi, A, Sali, Forbidden Configurations: Boundary Cases,
*European J. Combin.*,**35**(2014), 51-66. (pdf file) - R.P. Anstee, A survey of forbidden configuration results,
*Elec. J. of Combinatorics*,**20**(2013), DS20, 56pp. (pdf file) - R.P. Anstee, R. Chen, Forbidden Submatrices, some new bounds and constructions,
*Elec. J. of Combinatorics*,**20**(2013), P5, 13pp. (pdf file) - R.P. Anstee, M. Raggi, A, Sali, Evidence for a Forbidden Configuration Conjecture; one more case solved,
*Discrete Math.***312**(2012), pp. 2720-2729 - R.P. Anstee, M. Raggi, Genetic Algorithms applied to problems of Forbidden Configurations ,
*Elec. J. of Combinatorics*,**18**(2011), P230, 23pp. (pdf file) - R.P. Anstee, J. Blackman, H. Yang, Perfect matchings in grid graphs after vertex deletions,
*SIAM J of Discrete Mathematics*,**25**(2011), 1754-1767. - R.P. Anstee, Balin Fleming, Linear Algebra Methods for Forbidden Configurations,
*Combinatorica*,**31**(2011) 1-19. - R.P. Anstee, C.G.W. Meehan, Forbidden Configurations and Repeated Induction, Discrete Math., 311(2011), 2187-2197.
- R.P. Anstee, F. Barekat, A. Sali, Small Forbidden Configurations V: Exact Bounds for 4x2 cases,
*Studia Sci. Math. Hun.*,**48**(2011), 1-22. - R.P. Anstee, Balin Fleming, Two Refinements of the Bound of Sauer, Perles and Shelah, and Vapnik and Chevonenkis,
*Discrete Math.*,**310**(2010), 3318-3323. - R.P. Anstee, S.N. Karp, Forbidden Configurations: Exact bounds determined by critical substructures,
*Elec. J. of Combinatorics*,**17**(2010), R50, 27pp. - R.E.L.
Aldred, R.P. Anstee, S.C. Locke, Perfect matchings after vertex deletions,
*Discrete Math.***307**(2007), 3048-3054. - R.P. Anstee, N. Kamoosi, Small Forbidden Configurations III,
*Elec. J. Combin.***14**(2007), R79, (34pp). - R.P.
Anstee, A. Sali, Latin Squares and Low Discrepancy Allocation of two-dimensional data,
*European J. of Combin.***28**(2007), 2115-2124. - R.P. Anstee, Peter Keevash, Pairwise intersections and forbidden configurations,
*European J. of Combin.***27**(2006), 1235-1248. - R.P. Anstee, B. Fleming, Z. Furedi, and A. Sali, Color critical hypergraphs and forbidden configurations, proceedings of EuroComb 2005, Berlin, Germany.
*Discrete mathematics and Theoretical Computer Science,*2005, 117-122. - R.P.
Anstee, A. Sali, Small Forbidden Configurations IV,
*Combinatorica*,**25**(2005), 503-518. - R.P.
Anstee, R. Ferguson, J.R. Griggs, Circular Permutations with low
discrepancy k-sums,
*J. of Combinatorial Theory (A)*,**100**(2002), 302-321. - R.P.
Anstee, L. Ronyai, A. Sali, Shattering News,
*Graphs and Combinatorics*,**18**(2002),59-73. - R.P.
Anstee, R. Ferguson, A. Sali, Small Forbidden Configurations II,
*Electronic Journal of Combinatorics*Vol**8**(1), 2001, R4(25pp). - R.P.
Anstee, J. Demetrovics, G.O.H. Katona, A. Sali, Low Discrepancy Allocation
of Two Dimensional Data, in
*Foundations of Information and Knowledge Systems*, Proceedings of 1st FoIKS, Burg, Germany, Lecture Notes in Computer Science, v**1762**, Springer, 2000, 1-12.

(This has been referred to in US patent 6513100, System and Method for Fast Referencing a Reference counted item.) - R.P.
Anstee, On a Conjecture Concerning Forbidden Submatrices,
*J. Combin. Math and Combin. Comp.***32**(2000), 185-192. - R.P.
Anstee, V. Rumchev, Asymptotic Reachable Sets for Discrete-Time Positive
Linear Systems,
*Systems Science***25**(1999), 41-48. - R.P.
Anstee, Yunsun Nam: Convexity of Degree Sequences,
*J. Graph Theory,***30**(1999), 147-156. - R.P.
Anstee, Yunsun Nam: More Sufficient Conditions for a graph to have
factors,
*Discrete Math.***184**(1998), 15-24. - R.P.
Anstee, L. Caccetta: Orthogonal Matchings,
*Discrete Math.***179**(1998), 37-47. - R.P.
Anstee, L. Caccetta: Recognizing Diameter Critical Graphs, in
*Combinatorics, Complexity and Logic: Proceedings of Discrete Mathematics and Theory of Computer Science '96,*Springer, 1997, 105-112. - R.P.
Anstee, J.R. Griggs and A. Sali: Small Forbidden Configurations
*Graphs and Combinatorics,***13**(1997), 97-118. - R.P.
Anstee, A. Sali: Sperner families of bounded VC-dimension,
*Discrete Math.***175**(1997), 13-21. - R.P.
Anstee: Dividing a graph by degrees,
*J. Graph Theory,***23**(1996), 377-384. - R.P.
Anstee, J.R. Griggs: An application of Matching Theory to edge colourings,
*Discrete Math.***156**(1996), 253-256. - R.P.
Anstee: Forbidden Configurations: Induction and Linear Algebra,
*European J. Of Combin.***16**(1995), 427-438. - R.E.L.
Aldred, R.P. Anstee: On the density of sets of divisors,
*Discrete Math.***137**(1995), 345-349. - R.P.
Anstee: Minimum vertex weighted deficiency of (g,f)-factors,
*Discrete Appl. Math.***44**(1993), 247-260. - R.P.
Anstee: Matching Theory: Fractional to Integral,
*N.Z. J. of Math.***21**(1992), 17-32. - R.P.
Anstee: Simplified Existence Theorems for (g,f)-factors,
*Discrete Appl. Math.***27**(1990), 29-38. - R.P.
Anstee: Forbidden Configurations, determinants and discrepancy,
*European J. of Combin.***11**(1990), 15-19. - R.P.
Anstee, J.H. Przytycki and D. Rolfsen: Knot Polynomials and generalized
mutation,
*Topology and its Applics.***32**(1989), 237-249. - R.P.
Anstee: A Forbidden Configuration Theorem of Alon,''
*J. of Combinatorial Theory***Ser.A 47**(1988), 16-27. - R.P.
Anstee, M. Farber: On Bridged Graphs and Cop-win Graphs,
*J. of Combinatorial Theory (B)***44**(1988), 22-28. - R.P.
Anstee: A Polynomial Algorithm for
*b*-Matching: An Alternative Approach,''*Information Processing Letters***24**(1987), 153-157. - R.P.
Anstee, Z. Furedi: Forbidden Submatrices,
*Discrete Math***62**(1986), 225-243. - R.P.
Anstee: Invariant Sets of Arcs in Network Flow Problems,
*Discrete Applied Math.***13**(1986), 1-7. - R.P.
Anstee: General Forbidden Configuration Theorems,
*J. of Combinatorial Theory (A)***40**(1985), 108-124. - R.P.
Anstee, U.S.R. Murty: Matrices with Forbidden Subconfigurations,
*Discrete Math.***54**(1985), 113-116. - R.P.
Anstee: An Algorithmic Proof of Tutte's f-factor Theorem,
*J. of Algorithms***6**(1985), 112-131. - R.P.
Anstee, M. Farber: Characterizations of Totally Balanced Matrices,
*J. of Algorithms***5**(1984), 215-230. - R.P.
Anstee, Hypergraphs with no special cycles,
*Combinatorica***3**(1983), 141-146. - R.P.
Anstee, The Network Flows approach for matrices with given row and column
sums,
*Discrete Math.***44**(1983), 125-138. - R.P.
Anstee, Extensions of the notion of conformality in hypergraphs,
*Congressus Numerantium***39**(1983), 82-88. - R.P.
Anstee, Properties of a class of (0,1)-matrices covering a given matrix,
*Can. J. Math.***34**(1982), 438-453. - R.P.
Anstee, Triangular (0,1)-matrices with prescribed row and column sums,
*Discrete Math.***40**(1982), 1-10. - R.P.
Anstee, Properties of (0,1)-matrices without certain configurations,
*J. of Combinatorial Theory (A)***31**(1981), 256-269. - R.P.
Anstee, Properties of (0,1)-matrices with no triangles,
*J. of Combinatorial Theory (A)***29**(1980), 186-198. - R.P.
Anstee, Marshall Hall Jr., John G. Thompson, Planes of Order 10 do not
have a collineation of order 5,
*J. of Combinatorial Theory (A)***29**(1980), 39-58. - R.P.
Anstee, An analogue of group divisible designs for Moore Graphs,
*J. of Combinatorial Theory (B)***30**(1980), 11-20. - R.P.
Anstee, Properties of (0,1)-matrices with forbidden configurations,
Proceedings of Joint Canada-France Combinatorial Colloquium,
*Annals of Discrete Math.***9**(1980), 177-179.

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

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