The Approximate Loebl--Komlós--Sós Conjecture IV: Embedding Techniques and the Proof of the Main Result
| Autor: | János Komlós, Endre Szemerédi, Diana Piguet, Maya Stein, Jan Hladký, Miklós Simonovits |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Conjecture Dense graph General Mathematics Existential quantification 010102 general mathematics 0102 computer and information sciences 01 natural sciences Tree embedding Graph Extremal graph theory Combinatorics 010201 computation theory & mathematics Mathematics - Combinatorics Embedding 0101 mathematics Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics. 31:1072-1148 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/140982878 |
| Popis: | This is the last paper of a series of four papers in which 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 $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first two papers of this series, we decomposed the host graph $G$, and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure, and proved that any graph satisfying the conditions of the above approximate version of the Loebl-Komlos-Sos Conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations. Comment: 81 pages, 12 figures. A fix reflecting the change of Preconfiguration Clubs in Paper III, additional small changes |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|