UNIVERSALITY OF RANDOM GRAPHS

We prove that asymptotically (as n -> infinity) almost all graphs with n vertices and C(d)n(2-1/2d) log(1/d) n edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.

Riemannian Submersions with Discrete Spectrum

We prove some estimates on the spectrum of the Laplacian of the total space of a Riemannian submersion in terms of the spectrum of the Laplacian of the base and the geometry of the fibers. When the fibers of the submersions are compact and minimal, we prove that the spectrum of the Laplacian of the total space is discrete if and only if the spectrum of the Laplacian of the base is discrete. When the fibers are not minimal, we prove a discreteness criterion for the total space in terms of the relative growth of the mean curvature of the fibers and the mean curvature of the geodesic spheres in the base. We discuss in particular the case of warped products.

How far is C-0(Gamma, X) with Gamma discrete from C-0(K, X) spaces?

For a locally compact Hausdorff space K and a Banach space X we denote by C-0(K, X) the space of X-valued continuous functions on K which vanish at infinity, provided with the supremum norm. Let n be a positive integer, Gamma an infinite set with the discrete topology, and X a Banach space having non-trivial cotype. We first prove that if the nth derived set of K is not empty, then the Banach-Mazur distance between C-0(Gamma, X) and C-0(K, X) is greater than or equal to 2n + 1. We also show that the Banach-Mazur distance between C-0(N, X) and C([1, omega(n)k], X) is exactly 2n + 1, for any positive integers n and k. These results extend and provide a vector-valued version of some 1970 Cambern theorems, concerning the cases where n = 1 and X is the scalar field.