• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Logical limit laws for minor-closed classes of graphs
【24h】

Logical limit laws for minor-closed classes of graphs

机译：用于次要封闭图形图形的逻辑极限法

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

摘要

Let g be an addable, minor-closed class of graphs. We prove that the zero-one law holds in monadic second-order logic (MSO) for the random graph drawn uniformly at random from all connected graphs in g on n vertices, and the convergence law in MSO holds if we draw uniformly at random from all graphs in g on n vertices. We also prove analogues of these results for the class of graphs embeddable on a fixed surface, provided we restrict attention to first order logic (FO). Moreover, the limiting probability that a given FO sentence is satisfied is independent of the surface S. We also prove that the closure of the set of limiting probabilities is always the finite union of at least two disjoint intervals, and that it is the same for FO and MSO. For the classes of forests and planar graphs we are able to determine the closure of the set of limiting probabilities precisely. For planar graphs it consists of exactly 108 intervals, each of the same length approximate to 5.39 10(-6). Finally, we analyse examples of non-addable classes where the behaviour is quite different. For instance, the zero-one law does not hold for the random caterpillar on n vertices, even in FO. (C) 2018 Elsevier Inc. All rights reserved.
机译：设g是一个可添加的次要封闭的图表。我们证明，零一法在MonadiC二阶逻辑（MSO）中持有，随机从N顶点的G上的所有连接图均匀地绘制，并且如果我们随机地均匀地绘制，MSO中的收敛法n顶点的g中的所有图表。只要我们限制了关注第一阶逻辑（FO），我们还将这些结果的类别证明了这些结果的类似物。此外，满足给定Fo句子的限制概率是独立于表面S.我们还证明了该组限制概率的关闭始终是至少两个不相交的间隔的有限联合，并且它是相同的佛和mso。对于森林和平面图的类，我们能够精确地确定限制概率集的关闭。对于平面图，它由恰好108个间隔组成，每个间隔相同的长度近似为5.39 10（-6）。最后，我们分析了行为完全不同的不可添加类的示例。例如，零一法在N顶点上的随机毛虫不保持，即使在FO中也是如此。 （c）2018年Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号