| In this Ph.D. dissertation, 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 concerns the quantity fDelta(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 fDn infinityn=1 for any prescribed Delta. Although the Triangle Conjecture has long been refuted, we present an asymptotic version of it and prove it. The second problem involves the enumeration of spanning trees in grid graphs---graphs of the form G x Pn (or Cn) 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 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. |
