...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >The number of graphs without forbidden subgraphs
【24h】

The number of graphs without forbidden subgraphs

机译：没有禁止子图的图数

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

摘要

Given a family L of graphs, set p = p(L) = min(Lis an element ofL) chi(L) - 1 and, for n greater than or equal to 1, denote by P(n, L) the set of graphs with vertex set [n] containing no member of L as a subgraph, and write ex(n, L) for the maximal size of a member of P(n, L). Extending a result of Erdos, Frankl and Rodl (Graphs Combin. 2 (1986) 113), we prove thatP(n, L) less than or equal to 2(1/2(1-1/p)n2+O(n2-r))for some constant gamma = gamma(L) > 0, and characterize gamma in terms of some related extremal graph problems. In fact, if ex(n, L) = O(n(2-delta)), then any gamma < delta will do. Our proof is based on Szemeredi's Regularity Lemma and the stability theorem of Erdos and Simonovits. The bound above is essentially best possible. (C) 2003 Elsevier Inc. All rights reserved.
机译：给定一个图族L，设置p = p（L）= min（是L的元素）chi（L）-1，并且对于n大于或等于1的情况，用P（n，L）表示顶点集[n]不包含L的成员作为子图的图，并为ex（n，L）写出P（n，L）的成员的最大大小。扩展Erdos，Frankl和Rodl的结果（Graphs Combin。2（1986）113），我们证明 P（n，L）小于或等于2（1/2（1-1 / p）n2 + O（n2-r））对于某些常数gamma = gamma（L）> 0，并根据一些相关的极值图问题来表征gamma。实际上，如果ex（n，L）= O（n（2-delta）），则任何gamma

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号