...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Electronic Research Announcements in Mathematical Sciences >The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
【24h】

The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs

机译：稀疏图中的近似Loebl-Komlós-Sós猜想和嵌入树

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Loebl, Komlós and Sós conjectured that every $n$-vertex graph $G$ with at least $n/2$ verticesof degree at least $k$ contains each tree $T$ of order $k+1$ as asubgraph. We give a sketch of a proof of the approximate version of this conjecture for large values of $k$.? ? For our proof, we use a structural decomposition which can be seen as an analogue of Szemerédi's regularity lemma for possibly very sparse graphs. With this tool, each graph can be decomposed into four parts: a set of vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. We then exploit the properties of each of the parts of $G$ to embed a given tree $T$.? ? The purpose of this note is to highlight the key steps of our proof. Details can be found in [arXiv:1211.3050].
机译：Loebl，Komlós和Sós猜想，每个$ n $-顶点图$ G $的度数至少为$ n / 2 $顶点且至少为$ k $的子树都将顺序为$ k + 1 $的每棵树T $$作为子图。我们给出了对于$ k $的大值此猜想的近似版本的证明草图。 ？为了证明这一点，我们对可能非常稀疏的图使用结构分解，可以将其视为Szemerédi正则引理的类似物。使用此工具，每个图都可以分解为四个部分：一组高度度高的顶点，规则对（在规则性引理的意义上）和另外两个具有特定扩展特性的对象。然后，我们利用$ G $的每个部分的属性来嵌入给定的树$ T $。 ？本注释的目的是强调我们证明的关键步骤。可以在[arXiv：1211.3050]中找到详细信息。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号