All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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