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 III: The finer structure of LKS graphs. SIAM JOURNAL ON DISCRETE MATHEMATICS, 31 (2). pp. 1017-1071. ISSN 0895-4801
|
Text
1408.3866v3.pdf Download (1MB) | Preview |
Abstract
This is the third 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 paper of the series, we gave a decomposition of the graph G into several parts of different characteristics. In the second paper, we found a combinatorial structure inside the decomposition. In this paper, we will give a refinement of this structure. In the fourth paper, the refined structure will be used for embedding the tree T. © 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: TA 309/2-1, DFG, California Department of Fish and Game N1 Funding details: 1140766 N1 Funding details: :67985807 N1 Funding details: Marie Curie Cancer Care N1 Funding details: 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: P10-024F N1 Funding details: 78439, GACR, Grantová Agentura České Republiky N1 Funding details: NTIS -, ERDF, European Regional Development Fund N1 Funding details: CZ.1.05/1.1.00/02.0090 N1 Funding details: 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 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 Computer Science of the Czech Academy of Sciences is supported by RVO:67985807. 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 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 third author was partially supported by the Czech Science Foundation, grant GJ16-07822Y. 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 Coordinac?on 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:56 |
| Last Modified: | 12 Feb 2018 02:56 |
| URI: | http://real.mtak.hu/id/eprint/74257 |
Actions (login required)
 |
Edit Item |
