The approximate Loebl-Komlós--Sós conjecture and embedding trees in sparse graphs

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/67985807:_____/15:00443855

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

The approximate Loebl-Komlós--Sós conjecture and embedding trees in sparse graphs

Popis výsledku v původním jazyce

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].

Název v anglickém jazyce

The approximate Loebl-Komlós--Sós conjecture and embedding trees in sparse graphs

Popis výsledku anglicky

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].

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Electronic Research Announcements in Mathematical Sciences

ISSN

1935-9179

e-ISSN

—

Svazek periodika

22

Číslo periodika v rámci svazku

April

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

1-11

Kód UT WoS článku

000361819700001

EID výsledku v databázi Scopus

2-s2.0-84937435535