As> iVinf^ b^ where dx denotes the degree of the vertex x. In particular, we derive lower bounds of eigenvalues for convex subgraphs which consist of lattice points in an d-dimensional Riemannian manifolds M with convex boundary. The techniques involve both the (discrete) heat kernels of graphs and improved estimates of the (continuous) heat kernels of Riemannian manifolds. We prove eigenvalue lower bounds for convex subgraphs of the form ce2/(dD (M)) 2 where e denotes the distance between two closest lattice points, D (M) denotes the diameter of the manifold M and c is a constant (independent of the dimension d and the number of vertices in 5, but depending on the how" dense" the lattice points are). This eigenvalue bound is useful for bounding the rates of convergence for various random walk problems. Since many enumeration problems can be approximated by considering random walks in convex subgraphs of some appropriate host graph, the eigenvalue inequalities here have many applications.

Simple-homotopy for cell complexes is a special type of topological homotopy constructed by elementary collapses and elementary expansions. In this paper, we introduce graph homotopy for graphs and Graham homotopy for hypergraphs and study the relation between the two homotopies and the simple-homotopy for cell complexes. The graph homotopy is useful to describe topological properties of discretized geometric figures, while the Graham homotopy is essential to characterize acyclic hypergraphs and acyclic relational database schemes.

Given a closed strictly convex hypersurface M in the Euclidean space I?"+*, the Gauss map of M defines a homeomorphism between M and the unit sphere S". Therefore the Gauss-Kronecker curvature of M can be transplanted via the Gauss map to a function defined on S". If this function is denoted by K, then Minkowski observed that K must satisfy the equation where xi are the coordinate functions on S". Minkowski then asked the converse of the problem. Namely, given a positive function K defined on S" satisfying the above integral conditions, can we find a closed strictly convex hypersurface whose curvature function is given by K? Minkowski solved the problem in the category of polyhedrons. Then AD Alexandrov and others solved the problem in general. However, this last solution does not provide any information about the regularity of the (unique) convex hypersurface even if we assume K is smooth. In the two