Richard Anstee

• Professor,      also Associate member of Computer Science Department
• 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; Fax: (604) 822-6074

Courses

Math 223 Section 101 Sep 2006 (Sept, 2004)
Math 340 Section 201 Jan 2006 (Jan , 2006)
Math 523 Section 201 Jan 2006 (Jan , 2006)

Careers Information for Undergraduates

Careers blurb

Research Interests

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

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

Forbidden Configurations

I am posting a draft survey article on Forbidden Configurations that collects a number of published results together, highlights the recent conjecture of Sali and myself, and identifies some other open problems. This is a work in progress at this stage and any comments are welcomed. A survey of Forbidden Configuration results (pdf file)

Research in Progress

Discrete Mathematics has burgeoned as an area of research in the last 70 years. 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.

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 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 authors (Tank Aldred, Laura Dunwoody, Jerry Griggs, Martin Farber, Ron Ferguson, Balin Fleming, Zoltan Furedi, Nima Kamoosi, Peter Keevash, U.S.R. Murty, L. Ronyai, Chris Ryan, and Attila Sali). 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. Recent work has found fast algorithms for determining diameter critical graphs.

Work in progress

• R.P. Anstee, Balin Fleming, Zoltan Furedi and Attila Sali. Color critical hypergraphs and forbidden configurations, submitted to Discrete math and Theoretical Computer Science, 6pp.
• R.P. Anstee, N. Kamoosi, Small Forbidden Configurations III, preprint, 20pp.
• R.P. Anstee, J. Madden, Finding d-critical spanning subgraphs, preprint, 10pp.
• R.P. Anstee, Some problems concerning forbidden configurations, preprint, 10pp.
• R.P. Anstee, A survey of forbidden configuration results, preprint, 36pp.
• R.P. Anstee, Yunsun Nam, Included and Excluded edges for regular factors.
• R.P. Anstee, Peter Keevash, Pairwise intersections and forbidden configurations, submitted to European J. of Combin.

Publications

• R.P. Anstee, R. 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, v1762, Springer, 2000, 1-12.
• 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.