• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >THE APPROXIMATE LOBEL-KOMLOS-SOS CONJECTURE I: THE SPARSE DECOMPOSITION
【24h】

THE APPROXIMATE LOBEL-KOMLOS-SOS CONJECTURE I: THE SPARSE DECOMPOSITION

机译：近似LOBEL-KOMLOS-SOS猜想I：稀疏分解

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

摘要

In a series of four papers we prove the following relaxation of the Loebl-Komlos-Sos conjecture: For every alpha > 0 there exists a number k(0) such that for every k > k(0), every n-vertex graph G with at least (1/2 + alpha) n vertices of degree at least (1 + alpha)k contains each tree T of order k as a subgraph. The method to prove our result follows a strategy similar to approaches that employ the Szemeredi regularity lemma: We decompose the graph G, find a suitable combinatorial structure inside the decomposition, and then embed the tree T into G using this structure. Since for sparse graphs G, the decomposition given by the regularity lemma is not helpful, we use a more general decomposition technique. We show that each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. In this paper, we introduce this novel decomposition technique. In the three follow-up papers, we find a suitable combinatorial structure inside the decomposition, which we then use for embedding the tree.
机译：在一系列四篇论文中，我们证明了Loebl-Komlos-Sos猜想的以下弛豫：对于每个alpha> 0，存在一个数k（0），使得对于每个k> k（0），每个n顶点图G具有至少（1/2 + alpha）n个顶点且度数至少（1 + alpha）k的顶点包含k阶的每个树T作为子图。证明我们结果的方法遵循与采用Szemeredi正则引理的方法类似的策略：分解图G，在分解过程中找到合适的组合结构，然后使用该结构将树T嵌入到G中。由于对于稀疏图G，由规则性引理给出的分解无济于事，因此我们使用一种更通用的分解技术。我们表明，每个图都可以分解为极大程度的顶点，规则对（在规则性引理的意义上）和另外两个具有特定扩展特性的对象。在本文中，我们介绍了这种新颖的分解技术。在三篇后续论文中，我们在分解中找到了合适的组合结构，然后将其用于嵌入树。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号