• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Games, graphs, and geometry.
【24h】

Games, graphs, and geometry.

机译：游戏，图形和几何。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：本论文涉及四个单独的主题：Hales-Jewett数的平衡对应物，k临界无三角形图的最大密度，欧几里得集对“侵蚀”操作具有弹性，以及可应用的局部引理的扩展对于Hales-Jewett数，我们的动力来自于渴望证明有无限多种“精致”的Tic-Tac-Toe游戏。粗略地说，这些游戏都没有玩家有简单的理由拥有获胜/抽奖策略。本文的第一部分涉及将著名的“ Hales-Jewett数”的界线转换为“ Halving Hales-Jewett数”（其平衡的版本）的界线，这给出了预期的博弈论结果。本文的一部分涉及k临界无三角形图：随着k的增大，它们是否具有平方边密度，与k无关？这个问题与关键图的密度研究和无三角形图的色数研究都有密切的联系。出乎意料的是，我们能够确定k≥6的k临界无三角形图的精确渐近密度，甚至对于无五边形和三角形的图也是如此。第三部分，我们将考虑对欧几里得空间中的集合，它大致表示集合边界附近的“舍弃”点的操作。最后，在第四部分中，我们将经典的Lovasz Local Lemma概括为“ Lefthanded”版本，粗略地说，它允许人们忽略依赖项“将“本地引理”应用到具有潜在顺序的不良事件时。这将使我们能够证明非重复序列上经典结果的博弈论类似物，这代表了本地引理在游戏中的首次成功应用。

著录项

  • 作者

    Pegden, Wesley.;

  • 作者单位

    Rutgers The State University of New Jersey - New Brunswick.;

  • 授予单位 Rutgers The State University of New Jersey - New Brunswick.;
  • 学科 Applied Mathematics.;Mathematics.
  • 学位 Ph.D.
  • 年度 2010
  • 页码 107 p.
  • 总页数 107
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

  • 入库时间 2022-08-17 11:36:56

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号