- Professor, also Associate member of Computer
- Member of UBC Vancouver Senate, Joint Faculties, 2008-2014
PDF, Waterloo (1980-1982)
URF, Waterloo (1982-1984)
Location: Mathematics Annex, 1114
Telephone: (604) 822-6105
Address: anstee at math dot ubc dot ca
Telephone: (604) 822-2666; Fax: (604) 822-6074
Most Recent Course Websites (on sabbatical July 2012-June 2013)
Math 184 Section 103C (Sept, 2013)
Math 443 Section 101 (Sept, 2013)
Math 223 Section 102 (Sept, 2011)
Math 340 Section 202 (Jan, 2012)
Math 441 Section 201 (Jan , 2011)
Math 523 Section 201 (Jan , 2011)
Math 104 Section 103 (Sept, 2006)
Various bits of Information (advice) for undergraduates is at the bottom of this page. My role as chief advisor is to be the advisor to the advisors but I may be able to help you 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)
Recent graduate students
Hangjun (Gavin) Yang MSc 2005
Miguel Raggi Ph.D. 2011
Christina Koch MSc 2013
Discrete Mathematics, Extremal Set Theory, Graph Theory, Matching Theory
Research in Progress
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
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.
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
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.
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.
Various Old (Beamer) Talks.
More recent talks below.
SIAM Discrete Mathematics Conference, Halifax, June 19, 2012. (pdf file)
Forbidden Configurations: A survey
Cal State San Marcos, October 23, 2012. (pdf file)
Families of Forbidden Configurations
U of South Carolina, February 21, 2013. (pdf file)
U of South Carolina, February 26, 2013. (pdf file)
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)
Work in progress
- R.P. Anstee, C. Koch, M. Raggi, A, Sali, Forbidden Configurations and Product Constructions, submitted to Graphs and Combinatorics, 21pp
- R.P. Anstee, F. Barekat, Design Theory and Some Non-simple Forbidden Configurations , submitted to Journal of Combinatorial Designs, 27pp. (pdf file)
- R.P. Anstee, J. Madden, Finding d-critical spanning subgraphs, preprint,
- 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, M. Raggi, A, Sali, Forbidden Configurations: Boundary Cases, European J. Combin, accepted, 20pp (pdf file)
- R.P. Anstee, A survey of forbidden configuration results, Elec. J. of Combinatorics, 20 (2013), DS20, 56pp.
- R.P. Anstee, R. Chen, Forbidden Submatrices, some new bounds and constructions, Elec. J. of Combinatorics, 20 (2013), P5, 13pp.
- 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.
- 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.
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).
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.
Anstee, A. Sali, Small Forbidden Configurations IV, Combinatorica , 25(2005),
Anstee, R. Ferguson, J.R. Griggs, Circular Permutations with low
discrepancy k-sums, J. of Combinatorial Theory (A) ,
Anstee, L. Ronyai, A. Sali, Shattering News, Graphs and Combinatorics,
Anstee, R. Ferguson, A. Sali, Small Forbidden Configurations II, Electronic
Journal of Combinatorics Vol 8(1), 2001, R4(25pp).
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, v1762, Springer, 2000, 1-12.
(This has been referred to in US patent 6513100, System and Method for Fast Referencing a Reference counted item.)
Anstee, On a Conjecture Concerning Forbidden Submatrices, J. Combin.
Math and Combin. Comp. 32(2000), 185-192.
Anstee, V. Rumchev, Asymptotic Reachable Sets for Discrete-Time Positive
Linear Systems, Systems Science 25(1999), 41-48.
Anstee, Yunsun Nam: Convexity of Degree Sequences, J. Graph Theory, 30(1999),
Anstee, Yunsun Nam: More Sufficient Conditions for a graph to have
factors, Discrete Math. 184(1998), 15-24.
Anstee, L. Caccetta: Orthogonal Matchings, Discrete Math. 179(1998),
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.
Anstee, J.R. Griggs and A. Sali: Small Forbidden Configurations Graphs
and Combinatorics, 13(1997), 97-118.
Anstee, A. Sali: Sperner families of bounded VC-dimension, Discrete
Math. 175(1997), 13-21.
Anstee: Dividing a graph by degrees, J. Graph Theory, 23(1996),
Anstee, J.R. Griggs: An application of Matching Theory to edge colourings,
Discrete Math. 156(1996), 253-256.
Anstee: Forbidden Configurations: Induction and Linear Algebra, European
J. Of Combin. 16(1995), 427-438.
Aldred, R.P. Anstee: On the density of sets of divisors, Discrete
Math. 137(1995), 345-349.
Anstee: Minimum vertex weighted deficiency of (g,f)-factors, Discrete
Appl. Math. 44(1993), 247-260.
Anstee: Matching Theory: Fractional to Integral, N.Z. J. of Math. 21(1992),
Anstee: Simplified Existence Theorems for (g,f)-factors, Discrete
Appl. Math. 27(1990), 29-38.
Anstee: Forbidden Configurations, determinants and discrepancy, European
J. of Combin. 11(1990), 15-19.
Anstee, J.H. Przytycki and D. Rolfsen: Knot Polynomials and generalized
mutation, Topology and its Applics. 32(1989),
Anstee: A Forbidden Configuration Theorem of Alon,'' J. of
Combinatorial Theory Ser.A 47(1988), 16-27.
Anstee, M. Farber: On Bridged Graphs and Cop-win Graphs, J. of
Combinatorial Theory (B) 44(1988), 22-28.
Anstee: A Polynomial Algorithm for b-Matching:
An Alternative Approach,'' Information Processing Letters 24(1987),
Anstee, Z. Furedi: Forbidden Submatrices, Discrete Math 62(1986),
Anstee: Invariant Sets of Arcs in Network Flow Problems, Discrete
Applied Math. 13(1986), 1-7.
Anstee: General Forbidden Configuration Theorems, J. of Combinatorial
Theory (A) 40(1985), 108-124.
Anstee, U.S.R. Murty: Matrices with Forbidden Subconfigurations, Discrete
Math. 54(1985), 113-116.
Anstee: An Algorithmic Proof of Tutte's f-factor Theorem, J. of
Algorithms 6(1985), 112-131.
Anstee, M. Farber: Characterizations of Totally Balanced Matrices, J.
of Algorithms 5(1984), 215-230.
Anstee, Hypergraphs with no special cycles, Combinatorica 3(1983),
Anstee, The Network Flows approach for matrices with given row and column
sums, Discrete Math. 44(1983), 125-138.
Anstee, Extensions of the notion of conformality in hypergraphs, Congressus
Numerantium 39(1983), 82-88.
Anstee, Properties of a class of (0,1)-matrices covering a given matrix, Can.
J. Math. 34(1982), 438-453.
Anstee, Triangular (0,1)-matrices with prescribed row and column sums, Discrete
Math. 40(1982), 1-10.
Anstee, Properties of (0,1)-matrices without certain configurations, J.
of Combinatorial Theory (A) 31(1981), 256-269.
Anstee, Properties of (0,1)-matrices with no triangles, J. of
Combinatorial Theory (A) 29(1980), 186-198.
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),
Anstee, An analogue of group divisible designs for Moore Graphs, J. of
Combinatorial Theory (B) 30 (1980), 11-20.
Anstee, Properties of (0,1)-matrices with forbidden configurations,
Proceedings of Joint Canada-France Combinatorial Colloquium, Annals of
Discrete Math. 9 (1980), 177-179.