RUcore Resource Object
RUcore Resource Object
PDF-1(758.35 KB)
TitleAutomated discovery and proof in three combinatorial problems
NameRaff, Paul (author), Zeilberger, Doron (chair), Roberts, Fred (internal member), Retakh, Vladimir (internal member), Sloane, Neil (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2009-10
Date Created2009
SubjectMathematics,
Combinatorial analysis,
Graph theory
DescriptionIn this Ph.D. disseration, 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 f_D(n), defined as the size of the largest subset of [n] avoiding differences in D. 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_D(n)} from 1 to infinity for any prescribed D. 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 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
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.
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.
NotePh.D.
NoteIncludes bibliographical references (p. 114-117)
Noteby Paul Raff
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.000051892
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work