Random walks supported on random points ofZ/nZ

Summary This paper considers random walks on the integers modn supported onk points and asks how long does it take for these walks to get close to uniformly distributed. Ifk is a constant, Greenhalgh showed that at least some constant timesn ^2/(k–1) steps are necessary to make the distance of the random walk from the uniform distribution small; here we show that ifn is prime, some constant timesn ^2/(k–1) steps suffice to make this distance small for almost all choices ofk points. The proof uses the Upper Bound Lemma of Diaconis and Shahshahani and some averaging techniques. This paper also explores some cases wherek varies withn. In particular, ifk=(logn) ^a , we find different kinds of results for different values ofa, and these results disprove a conjecture of Aldous and Diaconis.Research Supported in Part by a Rackham Faculty Fellowship at the University of Michigan     

Converse Sturm–Hurwitz–Kellogg theorem and related results

We prove that if Vⁿ is a Chebyshev system on the circle and f is a continuous real-valued function with at least n + 1 sign changes then there exists an orientation preserving diffeomorphism of S¹ that takes f to a function L²-orthogonal to V. We also prove that if f is a function on the real projective line with at least four sign changes then there exists an orientation preserving diffeomorphism of that takes f to the Schwarzian derivative of a function on . We show that the space of piecewise constant functions on an interval with values ± 1 and at most n + 1 intervals of constant sign is homeomorphic to n-dimensional sphere. To V. I. Arnold for his 70th birthday     

Submanifolds of positive Ricci curvature in a Euclidean space

In this paper we study the role of constant vector fields on a Euclidean space R ^n+p in shaping the geometry of its compact submanifolds. For an n-dimensional compact submanifold M of the Euclidean space R ^n+p with mean curvature vector field H and a constant vector field on R ^n+p , the smooth function is used to obtain a characterization of sphere among compact submanifolds of positive Ricci curvature (cf. main Theorem).      

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

The numerical stability of evaluation schemes for polynomials based on the lagrange interpolation form

For evaluation schemes based on the Lagrangian form of a polynomial with degreen, a rigorous error analysis is performed, taking into account that data, computation and even the nodes of interpolation might be perturbed by round-off. The error norm of the scheme is betweenn ² andn ²+(3n+7) _n , where _n denotes the Lebesgue constant belonging to the nodes. Hence, the error norm is of least possible orderO(n ²) if, for instance, the nodes are chosen to be the Chebyshev points or the Fekete points.     

Characterizations of Steiner points

To each convex compact A in Euclidian space Eⁿ there corresponds a point S (A) from Eⁿ such that 1) S(x) = x for x Eⁿ, 2) S(A + B) = S(A) + S(B), 3) S (A_i) , if A_i converges in the Hausdorff metric to the unit sphere in Eⁿ, then S(A) is the Steiner point of the set A. The theorem improves certain earlier results on characterizations of the Steiner point.Translated from Matematicheskie Zametki, Vol. 14, No. 2, pp. 243–247, August, 1973.In conclusion, I wish to express my appreciation to E. M. Semenov for his constant help with this work.     

On the Asymmetry Constant of a Body with Few Vertices

In this note, we show that a nondegenerated polytope in IR ⁿ with n + k, 1 k < n, vertices is far from any symmetric body. We provide the asymptotically sharp estimates for the asymmetry constant of such polytopes.     

Frame self-orthogonal Mendelsohn triple systems of type

A Mendelsohn triple system (MTS) corresponds to an idempotent semisymmetric Latin square (quasigroup) of the same order. A holey MTS is called frame self-orthogonal, briefly FSOMTS, if its associated holey semisymmetric Latin square is frame self-orthogonal. In this paper, we use FSOMTS(hⁿ) to denote an FSOMTS with n spanning holes of size h. The existence of FSOMTS(hⁿ) for h3 has been known with a few exceptions. We extend the existing results and determine the necessary and sufficient conditions for the existence of FSOMTS(hⁿ) for any h and n with some possible exceptions.     

Triangle Factors In Sparse Pseudo-Random Graphs

The goal of the paper is to initiate research towards a general, Blow-up Lemma type embedding statement for pseudo-random graphs with sublinear degrees. In particular, we show that if the second eigenvalue of a d-regular graph G on 3n vertices is at most cd ³/n ² log n, for some sufficiently small constant c > 0, then G contains a triangle factor. We also show that a fractional triangle factor already exists if < 0.1d ²/n. The latter result is seen to be best possible up to a constant factor, for various values of the degree d = d(n).* Supported by a USA-Israeli BSF grant, by a grant from the Israel Science Foundation and by a Bergmann Memorial Award. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich.     

Complete controllability

A linear autonomous control system in ⁿ is said to be completely controllable iff there existsT>0 such that eachx ⁿ can be steered to anyy ⁿ in timeT. This paper presents a geometric characterization of this property in the case in which there are constraints on the values which the control maps can assume. A necessary and sufficient condition to get instant controllability (i.e., complete controllability for anyT>0) is also derived. This condition generalizes the well-known Kalman condition to the constrained case.     

Approximating CVP to Within Almost-Polynomial Factors is NP-Hard

This paper shows the problem of nding the closest vector in an n-dimensional lattice to be NP-hard to approximate to within factor n ^{c/log log n} for some constant c > 0.     

Stable constant mean curvature hypersurfaces in ℝ n+1 and ℍ n+1(−1)

In this paper, we show that all complete stable hypersurfaces in ⁿ⁺¹(or ⁿ⁺¹ (-1)) (n = 3, 4, 5) with constant mean curvature H > 0 (or H > 1, respectively) and finite L ² norm of traceless second fundamental form are compact geodesic spheres. Keywords: stable hypersurface, constant mean curvature, isometric immersion, Bernstein theorem.*Supported by PolyU grant G-T575.**Partially supported by CNPq of Brazil.     

Strong Laws for Martingale Differences and Independent Random Variables

A strong law of large numbers (SLLN) for martingale differences {X _n,_n,n1} permitting constant, random or hybrid normalizations, is obtained via a related SLLN for their conditional variances E{X _n ² |_n-1}n1. This, in turn, leads to martingale generalizations of known results for sums of independent random variables. Moreover, in the independent case, simple conditions are given for a generalized SLLN which contains the classical result of Kolmogorov when the variables are i.i.d.     

The Busemann-Petty problem for arbitrary measures

The Busemann-Petty problem asks whether symmetric convex bodies in ⁿ with smaller (n–1)-dimensional volume of central hyperplane sections necessarily have smaller n-dimensional volume. The answer to this problem is affirmative for n4 and negative for n5. In this paper we generalize the Busemann-Petty problem to essentially arbitrary measure in place of the volume. We also present applications of the latter result by proving several inequalities concerning the measure of sections of convex symmetric bodies in ⁿ.Mathematics Subject Classification (2000): 52A15, 52A21, 52A38     

Algorithms for graphs of bounded treewidth via orthogonal range searching

We show that, for any fixed constant k3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlog^k−1n) time.We also show that, for any fixed constant k2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlog^k+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.     

On The Number Of Sets Of Cycle Lengths

A set S of integers is called a cycle set on {1, 2, . . .,n} if there exists a graph G on n vertices such that the set of lengths of cycles in G is S. Erds conjectured that the number of cycle sets on {1, 2, . . .,n} is o(2 ⁿ ). In this paper, we verify this conjecture by proving that there exists an absolute constant c 0.1 such that the number of cycle sets on {1, 2, . . .,n} is .     

Algorithms for Singleton Attractor Detection in Planar and Nonplanar AND/OR Boolean Networks

Singleton attractor (also called fixed point) detection is known to be NP-hard even for AND/OR Boolean networks (AND/OR BNs in short, i.e., BNs consisting of AND/OR nodes), where BN is a mathematical model of genetic networks and singleton attractors correspond to steady states. In our recent paper, we developed an O(1.787ⁿ) time algorithm for detecting a singleton attractor of a given AND/OR BN where n is the number of nodes. In this paper, we present an O(1.757ⁿ) time algorithm with which we succeeded in improving the above algorithm. We also show that this problem can be solved in time, which is less than O((1 + ∈)ⁿ) for any positive constant ∈, when a BN is planar. A preliminary version of this paper has appeared in Proc. 3rd International Conference on Algebraic Biology (AB2008) [27].     

Skew-symmetric association schemes with two classes and strongly regular graphs of type L 2n−1(4n−1)

A construction of a pair of strongly regular graphs ⁿ and ⁿ of type L _2n–1(4n–1) from a pair of skew-symmetric association schemes W, W of order 4n–1 is presented. Examples of graphs with the same parameters as ⁿ and ⁿ, i.e., of type L _2n–1(4n–1), were known only if 4n–1=p ³, where p is a prime. The first new graph appearing in the series has parameters (v, k, )=(225, 98, 45). A 4-vertex condition for relations of a skew-symmetric association scheme (very similar to one for the strongly regular graphs) is introduced and is proved to hold in any case. This has allowed us to check the 4-vertex condition for ⁿ and ⁿ, thus to prove that ⁿ and ⁿ are not rank three graphs if n>2.     

Halley and Newton are one step apart

One of the central problems of scientific computation is the efficient numerical solution of the system of n equations in n unknowns F (x) = 0 where F: Rⁿ → Rⁿ is sufficiently smooth. While Newton's method is usually used for solving such systems, third order methods will in general use fewer iterations than a second order method to reach the same accuracy. However, the number of arithmetic operations per iteration is higher for third order methods than second order methods. In this note we will consider the case where F = ∇f, where f is three times continuously differentiable. We will show that for a large class of sparse problems the ratio of the number of arithmetic operations of a third order method and Newton's method is constant per iteration. It is shown that when the structure of the tensor is induced by a general sparse structured Hessian matrix which gives no fill-ins when we use a direct method to solve a system of linear equations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Intersection queries in sets of disks

In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report allk disks intersecting a query line segment in timeO(n ⁺ +k), wheren is the number of disks,=log₂(1+5)–1 0.695, and is an arbitrarily small positive constant. If the segment is a full line, the query time becomesO(n +k). For intersecting disks we obtain anO(n logn) size data structure that can answer an intersection query in timeO(n ^2/3 log² n+k). We also present a linear size data structure for ray shooting queries, whose query time isO(n ).The research of the first two authors was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The work of the third author was supported byDimacs (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center — NSF-STC88-09648.