Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Automated Proof and Discovery in Three Combinatorial Problems (Ph.D. Thesis Defense)
Speaker: Paul Raff, Rutgers University
Date: Friday, August 14, 2009 11:00AM - Noon
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this Ph.D. defense, I will go over advances I have made in three combinatorial problems. The running theme throughout these three problems is the novel use of computers to aid not only in the discovery of the theorems proved, but also in the proofs themselves. The first problem involves the enumeration of spanning trees in grid graphs - graphs of the form G x P_n (or C_n) for arbitrary G. An enumeration scheme is developed based on the partitions of [n], yielding an algorithmic method to completely solve the sequence for any G. These techniques yield a surprising consequence: sequences obtained in this manner are divisibility sequences. The second problem concerns the quantity f_\Delta(n), defined as the size of the largest subset of [n] avoiding differences in \Delta. Originally motivated by the Triangle Conjecture of Schutzenberger and Perrin, we again define an enumeration scheme that will find, and prove automatically, the sequence {f_\Delta(n)} for any prescribed \Delta. Although the Triangle Conjecture has long been refuted, we present an asymptotic version of it and prove it. The final problem is the firefighter problem, a dynamic graph theory problem modeling the spread of diseases, information, etc. We will present the problem as it applies on the two-dimensional grid and prove new upper and lower bounds, found mainly through computer experimentation.
The thesis committee is led by Prof. Doron Zeilberger. Prof. Fred Roberts, Prof. Vladimir Retakh, and outside member Dr. Neil Sloane from Bell Labs are on the committee also. Demonstrations of the computer software will be shown, and all are welcome to attend.