The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F17%3A00474810" target="_blank" >RIV/67985807:_____/17:00474810 - isvavai.cz</a>
Alternative codes found
RIV/67985840:_____/17:00474810
Result on the web
<a href="http://dx.doi.org/10.1137/140982842" target="_blank" >http://dx.doi.org/10.1137/140982842</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/140982842" target="_blank" >10.1137/140982842</a>
Alternative languages
Result language
angličtina
Original language name
The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
—
Volume of the periodical
31
Issue of the periodical within the volume
2
Country of publishing house
US - UNITED STATES
Number of pages
38
Pages from-to
945-982
UT code for WoS article
000404770300021
EID of the result in the Scopus database
2-s2.0-85021932060