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 $(\frac{1}{2}+\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. In the three follow-up papers, we find a suitable combinatorial structure inside the decomposition, which we then use for embedding the tree.

This is the second of a series of four papers in which 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 $(\frac{1}{2}+\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 this 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 third and fourth papers, we refine the structure and use it for embedding the tree $T$.

This is the third of a series of four papers in which 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 $(\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 fourth paper, the refined structure will be used for embedding the tree $T$.

This is the last of a series of four papers in which 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 $(\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--Komlós--Sós conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations.

We describe a deterministic polynomial-time algorithm which, for a convex body K in Euclidean n-space, finds upper and lower bounds on K's diameter which differ by a factor of O(/spl radic/n/logn). We show that this is, within a constant factor, the best approximation to the diameter that a polynomial-time algorithm can produce even if randomization is allowed. We also show that the above results hold for other quantities similar to the diameter-namely; inradius, circumradius, width, and maximization of the norm over K. In addition to these results for Euclidean spaces, we give tight results for the error of deterministic polynomial-time approximations of radii and norm-maxima for convex bodies in finite-dimensional l/sub p/ spaces.

The authors give an O(n/sup 7/log/sup 2/n) randomised algorithm to approximate the volume of a convex body, and an O(n/sup 6/log n) algorithm to sample a point from the uniform distribution over a convex body. For convex polytopes the algorithm runs in O(n/sup 7/log/sup 4/n) steps. Several tools are developed that may be interesting on their own. They extend results of Sinclair-Jerrum (1988) and the authors (1990) on the mixing rate of Markov chains from finite to arbitrary Markov chains. They describe an algorithm to integrate a function with respect to the stationary distribution of a general Markov chain. They also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. In several previous positive and negative results, the problem of computing the diameter of a convex body behaved similarly as the volume problem. In contrast to this, they show that there is no polynomial randomized algorithm to compute the diameter within a factor of n/sup 1/4/.>

A. Sinclair and M. Jerrum (1988) derived a bound on the mixing rate of time-reversible Markov chains in terms of their conductance. The authors generalize this result by not assuming time reversibility and using a weaker notion of conductance. They prove an isoperimetric inequality for subsets of a convex body. These results are combined to simplify an algorithm of M. Dyer et al. (1989) for approximating the volume of a convex body and to improve running-time bounds.>