TY - JOUR
TI - Games, graphs, and geometry
DO - https://doi.org/doi:10.7282/T3XP751J
PY - 2010
AB - This 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.
KW - Mathematics
KW - Combinatorial geometry
KW - Games
KW - Charts, diagrams, etc
KW - Graph theory
LA - eng
ER -