Počet záznamů: 1
The approximate Loebl-Komlós--Sós conjecture and embedding trees in sparse graphs
- 1.
SYSNO ASEP 0443855 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název The approximate Loebl-Komlós--Sós conjecture and embedding trees in sparse graphs Tvůrce(i) Hladký, Jan (MU-W) RID, SAI, ORCID
Piguet, Diana (UIVT-O) RID, ORCID, SAI
Simonovits, M. (HU)
Stein, M. (CL)
Szemerédi, E. (US)Zdroj.dok. Electronic Research Announcements in Mathematical Sciences - ISSN 1935-9179
Roč. 22, April (2015), s. 1-11Poč.str. 11 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova extremal graph theory ; Loebl-Komlós-Sós conjecture ; regularity lemma Vědní obor RIV BA - Obecná matematika CEP 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy Institucionální podpora MU-W - RVO:67985840 ; UIVT-O - RVO:67985807 UT WOS 000361819700001 EID SCOPUS 84937435535 DOI 10.3934/era.2015.22.1 Anotace Loebl, Komlós and Sós conjectured that every n-vertex graph G with at least n/2 vertices of degree at least k contains each tree T of order k+1 as a subgraph. We give a sketch of a proof of the approximate version of this conjecture for large values of k. For our proof, we use a structural decomposition which can be seen as an analogue of Szemerédi's regularity lemma for possibly very sparse graphs. With this tool, each graph can be decomposed into four parts: a set of vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. We then exploit the properties of each of the parts of G to embed a given tree T. The purpose of this note is to highlight the key steps of our proof. Details can be found in [arXiv:1211.3050]. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2016
Počet záznamů: 1