Počet záznamů: 1  

The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition

  1. 1. 0474810 - MU-W 2018 RIV US eng J - Článek v odborném periodiku
    Hladký, Jan - Komlós, J. - Piguet, Diana - Simonovits, M. - Stein, M. - Szemerédi, E.
    The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition.
    SIAM Journal on Discrete Mathematics. Roč. 31, č. 2 (2017), s. 945-982. ISSN 0895-4801
    Grant CEP: GA MŠk(CZ) 1M0545
    GRANT EU: European Commission(XE) 628974 - PAECIDM
    Institucionální podpora: RVO:67985840 ; RVO:67985807
    Klíčová slova: extremal graph theory * Loebl–Komlós–Sós conjecture * regularity lemma
    Kód oboru RIV: BA - Obecná matematika; BA - Obecná matematika (UIVT-O)
    Obor OECD: Pure mathematics; Pure mathematics (UIVT-O)
    Impakt faktor: 0.717, rok: 2017
    http://epubs.siam.org/doi/10.1137/140982842

    In a series of four papers we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(0.5+alpha)n$ vertices of degree at least $(1+alpha)k$ contains each tree $T$ of order $k$ as a subgraph. The method to prove our result follows a strategy similar to approaches that employ the Szemerédi regularity lemma: We decompose the graph $G$, find a suitable combinatorial structure inside the decomposition, and then embed the tree $T$ into $G$ using this structure. Since for sparse graphs $G$, the decomposition given by the regularity lemma is not helpful, we use a more general decomposition technique. We show that each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. In this paper, we introduce this novel decomposition technique.
    Trvalý link: http://hdl.handle.net/11104/0271761
    Název souboruStaženoVelikostKomentářVerzePřístup
    Hladky4.pdf131.3 MBVydavatelský postprintvyžádat