Home
Resource
Automated discovery and proof in three combinatorial problems
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(758.35 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Raff, Paul. Automated discovery and proof in three combinatorial problems. Retrieved from https://doi.org/doi:10.7282/T3T72HM0

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

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
Date Created
Other Date2009-10 (degree)
SubjectMathematics, Combinatorial analysis, Graph theory
Extentx, 118 p. : ill.
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.
NotePh.D.
NoteIncludes bibliographical references (p. 114-117)
Noteby Paul Raff
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3T72HM0
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
Version 8.5.5
Rutgers University Libraries - Copyright ©2024