Počet záznamů: 1  

The approximate Loebl-Komlós--Sós conjecture and embedding trees in sparse graphs

  1. 1.
    SYSNO ASEP0443855
    Druh ASEPJ - Článek v odborném periodiku
    Zařazení RIVJ - Článek v odborném periodiku
    Poddruh JČlánek ve WOS
    NázevThe 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-11
    Poč.str.11 s.
    Jazyk dok.eng - angličtina
    Země vyd.US - Spojené státy americké
    Klíč. slovaextremal graph theory ; Loebl-Komlós-Sós conjecture ; regularity lemma
    Vědní obor RIVBA - Obecná matematika
    CEP1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy
    Institucionální podporaMU-W - RVO:67985840 ; UIVT-O - RVO:67985807
    UT WOS000361819700001
    EID SCOPUS84937435535
    DOI10.3934/era.2015.22.1
    AnotaceLoebl, 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
    KontaktJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Rok sběru2016
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.