ﻻ يوجد ملخص باللغة العربية
In a series of four papers we prove the following relaxation of the Loebl-Komlos-Sos 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 $(frac12+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 Szemeredi 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. In the three follow-up papers, we find a combinatorial structure suitable inside the decomposition, which we then use for embedding the tree.
Loebl, Komlos and Sos 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 l
We prove a version of the Loebl-Komlos-Sos Conjecture for dense graphs. For each q>0 there exists a number $n_0in mathbb{N}$ such that for any n>n_0 and k>qn the following holds: if G be a graph of order n with at least n/2 vertices of degree at leas
This is the third of a series of four papers in which we prove the following relaxation of the Loebl-Komlos-Sos 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 $(frac12+
This is the second of a series of four papers in which we prove the following relaxation of the Loebl-Komlos--Sos 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 $(frac1
This is the last paper of a series of four papers in which we prove the following relaxation of the Loebl-Komlos-Sos 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 $(fr