On Kauffman invariants for 6-valent graphs

An explicit way for producing invariants for 6-valent graphs with rigid vertices within the framework of Kauffman's approach to graph invariants is presented. These invariants can be used to detect the chirality of a 6-valent graph with rigid vertices. A relevant example is considered. Bibliography: 19 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 223, 1995, pp. 251–262. Translated by A. M. Nikitin     

A STRASSEN LAW OF THE ITERATED LOGARITHM FOR PROCESSES WITH INDEPENDENT INCREMENT

ＡＳＴＲＡＳＳＥＮＬＡＷＯＦＴＨＥＩＴＥＲＡＴＥＤＬＯＧＡＲＩＴＨＭＦＯＲＰＲＯＣＥＳＳＥＳＷＩＴＨＩＮＤＥＰＥＮＤＥＮＴＩＮＣＲＥＭＥＮＴＷａｎｇＪｉａｇａｎｇＡｂｓｔｒａｃｔＬｅｔＸ＝｛Ｘ（ｔ），ｔ０｝ｂｅａｐｒｏｃｅｓｗｉｔｈｉｎｄｅｐ...     

Optimal Planar Interception with Fixed End Conditions: Approximate Solutions

In a previous paper (Ref. 1), an exact solution of the optimal planar interception with fixed end conditions was derived in closed form. The optimal control was expressed as an explicit function of the state variables and two fixed parameters, obtained by solving a set of nonlinear algebraic equations involving elliptic integrals. In order to facilitate the optimal control implementation, the present paper derives a highly accurate simplified solution assuming that the ratio of the pursuer turning radius to the initial range is small. An asymptotic expansion further reduces the computational workload. Construction of a near-optimal open-loop control, based on the approximations, completes the present paper.     

Normalization and averaging on compact lie groups in nonlinear mechanics

We consider the method of normal forms, the Bogolyubov averaging method, and the method of asymptotic decomposition proposed by Yu. A. Mitropol’skii and the author of this paper. Under certain assumptions about group-theoretic properties of a system of zero approximation, the results obtained by the method of asymptotic decomposition coincide with the results obtained by the method of normal forms or the Bogolyubov averaging method. We develop a new algorithm of asymptotic decomposition by a part of the variables and its partial case — the algorithm of averaging on a compact Lie group. For the first time, it became possible to consider asymptotic expansions of solutions of differential equations on noncommutative compact groups.     

On Series of Ordinals and Combinatorics

This paper deals mainly with generalizations of results in finitary combinatorics to infinite ordinals. It is well-known that for finite ordinals ∑_bT<αβ is the number of 2-element subsets of an α-element set. It is shown here that for any well-ordered set of arbitrary infinite order type α, ∑_bT<αβ is the ordinal of the set M of 2-element subsets, where M is ordered in some natural way. The result is then extended to evaluating the ordinal of the set of all n-element subsets for each natural number n ≥ 2. Moreover, series ∑_β<αf(β) are investigated and evaluated, where α is a limit ordinal and the function f belongs to a certain class of functions containing polynomials with natural number coefficients. The tools developed for this result can be extended to cover all infinite α, but the case of finite α appears to be quite problematic.     

Probability for a Wiener process to reside in tube domains for a long period of time

We give various representations of asymptotics for the probability for a Wiener process to reside within a curvilinear strip during extended time intervals.     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.