The Approximate Loebl-Komlós-Sós Conjecture I: The Sparse Decomposition
The Approximate Loebl-Komlós-Sós Conjecture I: The Sparse Decomposition
复制标题
近似 Loebl-Komlós-Sós 猜想 I：稀疏分解
DOI：
10.1137/140982842
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
E. Szemerédi
中科院分区：
文献类型：
--
作者：
J. Hladký;J. Komlós;D. Piguet;M. Simonovits;M. Stein;E. Szemerédi
在一系列四篇文章中，我们证明了Loebl-Komlos-SOS猜想的下列松弛：对任何一个，都存在一个数，使得对每个至少有度顶点的顶点图，都包含每个阶树作为一个子图。证明我们结果的方法遵循了类似于使用Szemer\‘EDI正则性引理的方法：我们对图进行分解，在分解中找到合适的组合结构，然后将该结构嵌入到树中。由于对于稀疏图，由正则性引理给出的分解是没有帮助的，所以我们使用更一般的分解技术。我们证明了每个图都可以分解成巨度顶点、正则对(在正则性引理意义下)和另外两个对象，每个对象都表现出一定的展开性质。在本文中，我们介绍了这种新的分解技术。在后续的三篇论文中，我们在分解中找到了一个合适的组合结构，然后用它来嵌入树。
In a series of four papers we prove the following relaxation of the Loebl-Komlos-Sos Conjecture: For everythere exists a numbersuch that for everyevery-vertex graphwith at leastvertices of degree at leastcontains each treeof orderas a subgraph. The method to prove our result follows a strategy similar to approaches that employ the Szemer\'edi regularity lemma: we decompose the graph, find a suitable combinatorial structure inside the decomposition, and then embed the treeintousing this structure. Since for sparse graphs, 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 combinatorial structure suitable inside the decomposition, which we then use for embedding the tree.
登录
查看更多内容
矩阵和稀疏图的 Szemerédi 正则引理
DOI：
10.1017/s0963548310000490
发表时间：
2010
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
A. Scott
通讯作者：
A. Scott
影响因子：
1
作者：
Dan Hefetz;Michael Krivelevich;Tibor Szabó
通讯作者：
Tibor Szabó
近似Loebl-Komlós-Sós猜想四：嵌入技术和主要结果的证明
DOI：
10.1137/140982878
发表时间：
2014
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
J. Hladký;J. Komlos;Diana Piguet;M. Simonovits;M. Stein;E. Szemerédi
通讯作者：
E. Szemerédi
DOI：
10.37236/278
发表时间：
2010-01
期刊：
Electron. J. Comb.
影响因子：
--
作者：
J. Balogh;Béla Csaba;M. Pei;Wojciech Samotij
通讯作者：
J. Balogh;Béla Csaba;M. Pei;Wojciech Samotij
树的大小-拉姆齐数
影响因子：
1
作者：
P. Haxell;Y. Kohayakawa
通讯作者：
Y. Kohayakawa