The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition

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

Nalezeny alternativní kódy

RIV/67985840:_____/17:00474810

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

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í

2017

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

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Svazek periodika

31

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

38

Strana od-do

945-982

Kód UT WoS článku

000404770300021

EID výsledku v databázi Scopus

2-s2.0-85021932060