Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Approximate Loebl-Komlos-Sos Conjecture III: The finer structure of LKS graphs
105
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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+alpha)n$ vertices of degree at least $(1+alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of the series, we gave a decomposition of the graph $G$ into several parts of different characteristics. In the second paper, we found a combinatorial structure inside the decomposition. In this paper, we will give a refinement of this structure. In the forthcoming fourth paper, the refined structure will be used for embedding the tree $T$.
rate research
Read More
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 $(frac12+alpha)n$ vertices of degree at least $(1+alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of the series, we gave a decomposition of the graph $G$ into several parts of different characteristics; this decomposition might be viewed as an analogue of a regular partition for sparse graphs. In the present paper, we find a combinatorial structure inside this decomposition. In the last two papers, we refine the structure and use it for embedding the tree $T$.
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 large values of $k$. For our proof, we use a structural decomposition which can be seen as an analogue of Szemeredis 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].
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.
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 least k, then any tree of order k+1 is a subgraph of G.
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 $(frac12+alpha)n$ vertices of degree at least $(1+alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first two papers of this series, we decomposed the host graph $G$, and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure, and proved that any graph satisfying the conditions of the above approximate version of the Loebl-Komlos-Sos Conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
