Hladký, J. and Komlós, János and Pigue, D. and Simonovits, Miklós and Stein, M. and Szemerédi, Endre (2017) The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs. SIAM JOURNAL ON DISCRETE MATHEMATICS, 31 (2). pp. 983-1016. ISSN 0895-4801
|
Text
1408.3871v4.pdf Download (685kB) | Preview |
Abstract
This is the second 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 this series, we gave a decomposition of the graph G into several parts of different characteristics; this decomposition might be viewed as an analogue of a regular partition for sparse graphs. In the present paper, we find a combinatorial structure inside this decomposition. In the third and fourth papers, we refine the structure and use it 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: 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, Seventh Framework Programme N1 Funding details: University of Warwick N1 Funding details: CMM, Center on the Microenvironment and Metastasis, Cornell University N1 Funding details: 78439 N1 Funding details: NTIS -, ERDF, European Regional Development Fund N1 Funding details: :67985807, Haixi Institute, Chinese Academy of Sciences N1 Funding text: The Institute of Mathematics of the Czech Academy of Sciences is supported by RVO:67985840. The 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 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 agreement PIEF-GA-2009-253925. The work leading to this invention was supported by the European Regional Development Fund (ERDF), project quot;NTIS - New Technologies for the Information Society," European Centre of Excellence, CZ.1.05/1.1.00/02.0090. 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: | statistical analysis; mathematical analysis; Graph theory; sparse graphs; Graph decompositions; Trees (mathematics); Paper; 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:59 |
| Last Modified: | 12 Feb 2018 02:59 |
| URI: | http://real.mtak.hu/id/eprint/74258 |
Actions (login required)
 |
Edit Item |
