Home
Resource
Symbolic-computational methods in combinatorial game theory and Ramsey theory
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(483.60 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Thanatipanonda, Thotsaporn. Symbolic-computational methods in combinatorial game theory and Ramsey theory. Retrieved from https://doi.org/doi:10.7282/T30G3K3F

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleSymbolic-computational methods in combinatorial game theory and Ramsey theory
NameThanatipanonda, Thotsaporn (author); Zeilberger, Doron (chair); Retakh, Vladimir (internal member); Saks, Michael (internal member); Sloane, Neil (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2008
Other Date2008 (degree)
SubjectMathematics, Game theory, Ramsey theory
Extentix, 135 p. : ill.
DescriptionThis thesis is a contribution to the emerging fleld of experimental rigorous mathematics, where one uses symbolic computation to conjecture proof-plans, and then proceeds to verify the conjectured proofs rigorously. The proved results, in addition to their independent interest, should also be viewed as case studies in this budding methodology. We now proceed to described the specific results presented in this dissertation. We first develop a finite-state automata approach, implemented in a Maple package ToadsAndFrogs, for conjecturing, and then rigorously proving, values for large families of positions in Richard Guy's combinatorial game Toads and Frogs". In particular, we prove conjectures of Jeff Erickson. We also discuss the values of all positions with exactly one ¤;Ta¤¤Fa;Ta¤¤¤FFF;Ta¤¤Fb, Ta¤¤¤Fb. We next consider the generalized chess problem of checkmating a king with a king and a rook on an m x n board at a specific starting position. We analyze the fastest way to checkmate. We also consider a problem posed by Ronald Graham about the minimum number,
over all 2-colorings of [1; n], of generalized so-called Schur triples, i.e. monochromatic triples of the form (x; y; x + ay) a [greater than or equal to symbol] 1. (The case a = 1 corresponds to the classical Schur triples). In addition to giving a completely new proof of the already known case of a = 1, we show that the minimum number of such triples is at most n2 2a(a2+2a+3) +O(n)
when a [greater than or equal to symbol] 2. We also find a new upper bound for the minimum number, over all r-colorings of [1; n], of monochromatic Schur triples, for r [greater than or equal to symbol] 3. Finally, in yet a different direction, we find closed-form expressions for the second moment of the random variable
umber of monochromatic Schur triples" defined on
the sample space of all r-colorings of the first n integers, and second and even higher moments for the number of monochromatic complete graphs Kk in Kn. In addition to their considerable independent interest, these formulas would hopefully be instrumental
in improving the extremely weak known lower bounds for the asymptotics of Ramsey number.
NotePh.D.
NoteIncludes abstract
NoteVita
NoteIncludes bibliographical references
Noteby Thotsaporn "Aek" Thanatipanonda
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T30G3K3F
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