Symbolic-Computational Methods in Combinatorial Game Theory and Ramsey Theory. (Paperback)

This thesis is a contribution to the emerging field 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□□F a, 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 >= 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 n22a&parl0;a2+2a+3&parr0; + O(n) when a >= 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 >= 3. Finally, in yet a different direction, we find closed-form expressions for the second moment of the random variable "number 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.