RUcore Resource Object
RUcore Resource Object
PDF-1(1.13 MB)
TitleGames, graphs, and geometry
NamePegden, Wesley (author), Beck, József (chair), Kahn, Jeff (internal member), Zeilberger, Doron (internal member), Spencer, Joel (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2010
Date Created2010
SubjectMathematics,
Combinatorial geometry,
Games,
Charts, diagrams, etc,
Graph theory
DescriptionThis thesis concerns four separate topics: the balanced counterpart of the Hales-Jewett number, the maximal density of k-critical triangle-free graphs, Euclidean sets resilient to an 'erosion' operation, and an extension of the Local Lemma which can be applied in a game setting. For the Hales-Jewett number, our motivation comes from a desire to show that there are infinitely many 'delicate' Tic-Tac-Toe games. Roughly speaking, these are games where neither player has a simple reason for having a winning/drawing strategy. The first part of this thesis concerns the translation of bounds on the famous 'Hales-Jewett number' into bounds on the 'Halving Hales-Jewett number', its 'balanced' version, which give the desired game-theoretic consequences. The second part of this thesis concerns k-critical triangle-free graphs: can they have quadratic edge-density, independent of k as k grows large? This question has close connections both to the study of the density of critical graphs, and the study of the chromatic number of triangle-free graphs. Surprisingly, we are able to determine the exact asymptotic density of k-critical triangle-free graphs for k ≥ 6, and even for pentagon-and-triangle-free graphs. In the third part, we will consider a simple erosion operation on sets in Euclidean space, which roughly represents the operation of 'shaving off' points near the boundary of a set. We will give a complete characterization of sets whose shape is unchanged by this operation. Finally, in the fourth part, we will generalize the classical Lovasz Local Lemma to a 'Lefthanded' version, which, roughly speaking, allows one to ignore dependencies 'to the right' when making an application of the Local Lemma to bad events which have an underlying order. This will allow us to prove game-theoretic analogs of classical results on nonrepetitive sequences, representing the first successful applications of a Local Lemma to games.
NotePh.D.
NoteIncludes abstract
NoteVita
NoteIncludes bibliographical references
Noteby Wesley Pegden
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000053616
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.