Počet záznamů: 1
The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition
- 1.
SYSNO ASEP 0474810 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 I: The sparse decomposition Tvůrce(i) Hladký, Jan (MU-W) RID, SAI, ORCID
Komlós, J. (US)
Piguet, Diana (UIVT-O) RID, ORCID, SAI
Simonovits, M. (HU)
Stein, M. (CL)
Szemerédi, E. (HU)Zdroj.dok. SIAM Journal on Discrete Mathematics. - : SIAM Society for Industrial and Applied Mathematics - ISSN 0895-4801
Roč. 31, č. 2 (2017), s. 945-982Poč.str. 38 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 Obor OECD Pure mathematics Vědní obor RIV – spolupráce Ústav informatiky - 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 000404770300021 EID SCOPUS 85021932060 DOI 10.1137/140982842 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2018
Počet záznamů: 1