The approximate Loebl-Komlós--Sós conjecture and embedding trees in sparse graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00443855" target="_blank" >RIV/67985840:_____/15:00443855 - isvavai.cz</a>
Alternative codes found
RIV/67985807:_____/15:00443855
Result on the web
<a href="http://dx.doi.org/10.3934/era.2015.22.1" target="_blank" >http://dx.doi.org/10.3934/era.2015.22.1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.3934/era.2015.22.1" target="_blank" >10.3934/era.2015.22.1</a>
Alternative languages
Result language
angličtina
Original language name
The approximate Loebl-Komlós--Sós conjecture and embedding trees in sparse graphs
Original language description
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].
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
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
2015
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
Electronic Research Announcements in Mathematical Sciences
ISSN
1935-9179
e-ISSN
—
Volume of the periodical
22
Issue of the periodical within the volume
April
Country of publishing house
US - UNITED STATES
Number of pages
11
Pages from-to
1-11
UT code for WoS article
000361819700001
EID of the result in the Scopus database
2-s2.0-84937435535