Hladký, J. and Komlós, János and Piguet, D. and Simonovits, Miklós and Stein, M. and Szemerédi, Endre (2017) The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result. SIAM JOURNAL ON DISCRETE MATHEMATICS, 31 (2). pp. 1072-1148. ISSN 0895-4801
|
Text
1408.3870v3.pdf Download (1MB) | Preview |
Abstract
This is the last of a series of four papers in which we prove the following relaxation of the Loebl-Komlós-Sós conjecture: For every α > 0 there exists a number k0 such that for every k > k0, every n-vertex graph G with at least (1/2 + α)n vertices of degree at least (1 + α)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-Komlós-Sós conjecture contains one of ten specific configurations. In this paper we embed the tree T in each of the ten configurations. © 2017 the authors.
| Item Type: | Article |
|---|---|
| Additional Information: | N1 Funding details: EP/J501414/1 N1 Funding details: 11090141 N1 Funding details: EP/I026630/1, EPSRC, Engineering and Physical Sciences Research Council N1 Funding details: 628974, REA, Research Executive Agency N1 Funding details: 321104 N1 Funding details: PIEF-GA-2009-253925, FP7, Seventh Framework Programme N1 Funding details: 1M0545 N1 Funding details: P10-024F N1 Funding details: TA 309/2-1, DFG, California Department of Fish and Game N1 Funding details: 1140766 N1 Funding details: :67985840 N1 Funding details: Marie Curie Cancer Care N1 Funding details: FP7/2007-2013, FP7, Seventh Framework Programme N1 Funding details: University of Warwick N1 Funding details: CMM, Center on the Microenvironment and Metastasis, Cornell University N1 Funding details: CZ.1.05/1.1.00/02.0090 N1 Funding details: NTIS -, ERDF, European Regional Development Fund N1 Funding details: 78439, Haixi Institute, Chinese Academy of Sciences N1 Funding text: The first author's research leading to these results received funding from the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement 628974. Much of the work was done while the first author was supported by an EPSRC postdoctoral fellowship EP/I026630/1 while affiliated with DIMAP and the Mathematics Institute, University of Warwick. The Institute of Mathematics of the Czech Academy of Sciences is supported by RVO:67985840. The third author was supported by the Marie Curie fellowship FIST, DFG grant TA 309/2-1, Czech Ministry of Education project 1M0545, EPSRC award EP/D063191/1, and EPSRC Additional Sponsorship EP/J501414/1. The research leading to these results received funding from the European Union Seventh Framework Programme (FP7/2007- 2013) under grant agreement PIEF-GA-2009-253925. The work leading to this invention was supported by the European Regional Development Fund (ERDF), project "NTIS - New Technologies for the Information Society," European Centre of Excellence, CZ.1.05/1.1.00/02.0090. The Institute of Computer Science of the Czech Academy of Sciences is supported by RVO:67985807. The fourth author was supported by OTKA 78439, OTKA 101536, OTKA 116769, and ERC-AdG. 321104. The fifth author was supported by Fondecyt Iniciacion grant 11090141, Fondecyt Regular grant 1140766, CMM Basal, and Nucleo Milenio Informaci?n y Coordinaci?n en Redes ICM/FIC P10-024F. The sixth author was supported by OTKA 104483, OTKA 101536, and ERC-AdG. 321104. |
| Uncontrolled Keywords: | Graph theory; sparse graphs; Graph decompositions; Trees (mathematics); Tree embedding; sparse graph; Regularity lemma; Loebl-Komlós-Sós conjecture; Graph decomposition; Extremal graph theory |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 12 Feb 2018 02:50 |
| Last Modified: | 12 Feb 2018 02:50 |
| URI: | http://real.mtak.hu/id/eprint/74256 |
Actions (login required)
 |
Edit Item |
