Linking (n − 2)-dimensional panels inn-space II: (n − 2, 2)-frameworks and body and hinge structures

An (n – 1, 2)-framework inn-space is a structure consisting of a finite set of (n – 2)-dimensional panels and a set of rigid bars each joining a pair of panels using ball joints. A body and hinge (or (n + 1,n – 1)-) framework inn-space consists of a finite set ofn-dimensional bodies articulated by a set of (n – 2)-dimensional hinges, i.e., joints in 2-space, line hinges in 3-space, plane-hinges in 4-space, etc. In this paper we characterize the graphs of all rigid (n – 1, 2)- and (n + 1,n – 1)-frameworks inn-space. Rigidity here is statical rigidity or equivalently infinitesimal rigidity.     

Monodromy of Rational KZ Equations and Some Related Topics

A special class of integrable Fuchsian systems on C ⁿ related to KZ equations is considered. We survey the construction of such systems and the list of the structural properties their monodromy representations. The relation of the Fuchsian systems obtained by the Veselov construction assosiated with a deformation of the A _n–1-type root system and the Gauss–Manin connection of the natural projection C ⁿ C ^n–1 is described. In this case, we prove that the monodromy representation is equivalent to the Burau representation of the Artin braid group. For a deformations of the other root system, we introduce generalized Burau representations. We conjecture that the integrable Fuchsian systems related to essential new finite sets of the vectors described by Veselov and Chalykh are the result of the Klares–Schlesinger isomonodromic deformations (or transformation) of the integrable Fuchsian system related to the Coxeter root systems.     

Distribution of Cardinalities of Row Spaces of Boolean Matrices of Order n

Let R(A) denote the row space of a Boolean matrix A of order n. We show that if n 7, then the cardinality |R(A)| (2^n–1 - 2^n–5, 2^n–1 - 2^n–6) U (2^n–1 - 2^n–6, 2^n–1). This result confirms a conjecture in [1].AMS Subject Classification (1991): 05B20 06E05 15A36Support partially by the Postdoctoral Science Foundation of China.Dedicated to Professor Chao Ko on the occasion of his 90th birthday     

Reversible linear systems and their versal deformations

Let R be a fixed linear involution (R ²=id) of the spaceR ⁿ . A linear operator M is said to bereversible with respect to R if RM R=M^–1 and infinitesimally reversible with respect to R if M R=–RM. A linear differential equation dx/dt=B(t)x is said to be reversible with respect to R if V(t)R –RV(–t). We construct normal forms and versal deformations for reversible and infinitesimally reversible operators. The results are applied to describe the homotopy classes of strongly stable reversible linear differential equations with periodic coefficients. The analogous theory for linear Hamiltonian systems was developed by J. Williamson, M. G. Krein, I.M. Gel'fand, V. B. Lidskii, D. M. Galin, and H. Koçak.Translated fromTrudy Seminara imeni I. G. Petrovskogo, No. 15, pp. 33–54, 1991. Original article submitted April 27, 1988.     

Eventually areally meanp-valent functions

Theorems concerning areally meanp-valent functions are extended to eventually areally meanp-valent functions. In particular, suppose is eventually areally meanp-valent in the unit disc,b, c are positive integers,a≧max {p−1, 0}. If |a _n|≦Cn ^α for alln=bm+c,m=1, 2, …, then |a _n|≦C′n ^α for alln. This is a marked extension of results due to Goluzin and to Hayman.     

New Cyclic Difference Sets with Singer Parameters Constructed from d-Homogeneous Functions

In this paper, for a prime power q, new cyclic difference sets with Singer para- meters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed by using q-ary sequences (d-homogeneous functions) of period q ⁿ –1 and the generalization of GMW difference sets is proposed by combining the generation methods of d-form sequences and extended sequences. When q is a power of 3, new cyclic difference sets with Singer parameters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed from the ternary sequences of period q ⁿ –1 with ideal autocorrelation introduced by Helleseth, Kumar, and Martinsen.     

Partial geometries and the triality quadric

Up to now there are eight partial geometries pg(7,8,4) known. Their point graphs as well as their block graphs are all related to the triality quadric Q⁺(7,2). We prove that some of these graphs are the point graph of (up to isomorphism) exactly one partial geometry. We investigate the relations among some of these eight partial geometries. Generalizing our results, we construct two new families of partial geometries pg(2^2n–1– 1, 2^2n–1, 2^2n–2).The second author is a Research Fellow supported by the Flemish Institute for the Promotion of Scientific and Technological Research in Industry (IWT), grant No. IWT/SB/971002.     

On some classes of algebraic surfaces with an infinite set of subspaces of skew symmetry

Special classes of (m – 1)-dimensional algebraic surfaces F ⁿ in a space E^m with inifinite set ofsubspaces of skew symmetry (in particular, orthogonal) are studied. It is assumed that directions of symmetry, as a rule, are asymptotic for F _n .Translated from Dinamicheskie Sistemy, No. 8, pp. 119–126, 1989.     

A properly invariant theory of infinitesimal deformations of an elastic Cosserat point

Summary In the context of a mechanical theory of a Cosserat point developed by Green and Naghdi [1=Quart. J. Mech. and Appl. Math.,44, 335–355 (1991)], this paper establishes a properly invariant theory for infinitesimal deformations. The invariant theory is valid for an elastic Cosserat point with an arbitrary number of directors. Its construction is based on a method developed by Casey and Naghdi [2=Arch. Rational Mech. Anal.,76, 355–391 (1981)] for unconstrained non-polar elastic bodies.     

On Recognition by Spectrum of Finite Simple Linear Groups over Fields of Characteristic 2

A finite group G is said to be recognizable by spectrum, i.e., by the set of element orders, if every finite group H having the same spectrum as G is isomorphic to G. We prove that the simple linear groups L _n (2^k) are recognizable by spectrum for n = 2^m ≥ 32.Original Russian Text Copyright © 2005 Vasil’ev A. V. and Grechkoseeva M. A.The authors were supported by the Russian Foundation for Basic Research (Grant 05-01-00797), the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-2069.2003.1), the Program “ Development of the Scientific Potential of Higher School” of the Ministry for Education of the Russian Federation (Grant 8294), the Program “Universities of Russia” (Grant UR.04.01.202), and a grant of the Presidium of the Siberian Branch of the Russian Academy of Sciences (No. 86-197).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 749–758, July–August, 2005.     

An improved algorithm for selecting <Emphasis Type="Italic">p</Emphasis> items with uncertain returns according to the minmax-regret criterion

We consider the problem of selecting a subset of p investments of maximum total return out of a set of n available investments with uncertain returns, where uncertainty is represented by interval estimates for the returns, and the minmax regret objective is used. We develop an algorithm that solves this problem in O(min{p,n–p}n) time. This improves the previously known complexity O(min{p,n–p}²n).This research has been supported by the Spanish Science and Technology Ministry and FEDER Grant No. BFM2002-04525-C02-02.Received: October 2002 / Accepted: September 2003     

The Number of Steps in the Robinson-Schensted Algorithm

Suppose that a permutation σ ∈ S _n is chosen at random (n is large) and the Robinson-Schensted algorithm is applied to compute the associated Young diagram. Then for almost all permutations the number of bumping operations performed by the algorithm is about (128/27π²)n ^3/2, and the number of comparison operations is about (64/27π²)n ^3/2 log₂ n.__________Translated from Funktsional’nyi Analiz i Ego Prilozheniya, Vol. 39, No. 2, pp. 82–86, 2005Original Russian Text Copyright © by D. Romik     

On the relations between infinitesimal bendings of different orders

It is established that if a surface has only one nontrivial independent field of first order infinitesimal bendings, then rigidity of order n 3 implies rigidity of any order m n, in particular, nondeformability that is analytic in parameter. All the considerations are carried out in class C ¹.In passing, a new approach to the determination of infinitesimal bendings of higher order is given. Translated from Ukrainskii Geometricheskii Sbornik, No. 35, pp. 118–124, 1992.     

Pointwise estimation of comonotone approximation

We prove that, for a continuous functionf(x) defined on the interval [–1,1] and having finitely many intervals where it is either nonincreasing or nondecreasing, one can always find a sequence of polynomialsP _n (x) with the same local properties of monotonicity as the functionf(x) and such that ¦f(x)–P _n (x) ¦C₂(f;n^–2+n ^–11–x ²), whereC is a constant that depends on the length of the smallest interval.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 11, pp. 1467–1472, November, 1994.The author is grateful to Prof. I. A. Shevchuk for his permanent attention to the work.     

On the nilpotency class of a multiplicative group of a modular group algebra of a dihedral 2-group

It is proved that the wreath product of a second-order group and the commutant of a dihedral group is imbedded into a multiplicative group of a modular group algebra of a dihedral group of order 2 ⁿ . This implies that the nilpotency class of the multiplicative group is equal to 2 ^n–2, i.e., to the order of the commutant of the dihedral group.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 1, pp. 39–45, January, 1995.     

On derivative-dependent infinitesimal deformations of differentiable maps

We study, by means of flows in jet bundles, infinitesimal deformations of germs of $\text{b}$^∞ maps $\text{?:R}{}^{\mathrm{n}}\text{→R}{}^{\mathrm{m}}$ that depend on a finite number of derivatives of these maps. We show that for m = 1 such deformations cannot essentially depend on derivatives higher than the first and that the deformations generalize the notion of an infinitesimal contact transformation. Analogous results hold for m > 1. Some applications to differential equations are given.     

Solution to the lighting problem for zone bodies

In the paper, the class of zone bodies, which includes, in particular, zonoids (and zonohedrons) is introduced. The lighting problem for this class is solved, thus generalizing earlier results for zonohedrons (H.Martini) and zonoids (V. G. Boltyanskii and P. S. Soltan). Namely, it is proved that the boundary of anyn-dimensional zone body other than a parallelepiped can be lit by 3·2 ^n–2 pencils of parallel rays or less.Translated fromMatematicheskie Zametki, Vol. 58, No. 4, pp. 505–511, November, 1995.This work was partially supported by the International Science Foundation under grant No. MAT6565-0925.     

The degree of a mapping in some problems of combinatorial geometry

The problem of dividing a unit mass that is continuously distributed inR ⁿ into various ratios by a pencil ofn+1 solid angles is connected with the question of the possibility of homotopies between certain coverings of the sphereS ^n–1. We prove that it is possible to inscribe a simplex homothetic to a given simplex in any convex solid region with a smooth boundary. In all the proofs we use the concept of the degree of special mappings onto a canonical simplex and its boundary. One figure.Translated from Ukrainskií Geometricheskií Sbornik, No. 30, 1987, pp. 62–66.     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

Constructive proofs of theorems relating to:F(x) = y,with applications

Some theorems are given which relate to approximating and establishing the existence of solutions to systemsF(x) = y ofn equations inn unknowns, for variousy, in a region of euclideann-space E ⁿ . They generalize known theorems.Viewing complementarity problems and fixed-point problems as examples, known results or generalizations of known results are obtained.A familiar use is made of homotopies H: E ⁿ × [0, 1]E ⁿ of the formH(x, t) = (1 –t)F ⁰ (x) + t[F(x) – y] where theF ⁰ in this paper is taken to be linear. Simplicial subdivisionsT ^k of E ⁿ × [0, 1] furnish piecewise linear approximatesG ^k toH. The basic computation is via the generation of piecewise linear curvesP ^k which satisfyG ^k (x, t) = 0. Visualizing a sequence {T ^k } of such subdivisions, with mesh size going to zero, arguments are made on connected, compact limiting curvesP on whichH(x, t) = 0.This paper builds upon and continues recent work of C.B. Garcia.The authors respectively: A. Charnes, research partially supported by Proj. No. NR047-021 Contract N00014-75-C-0269; C.B. Garcia, C.E. Lemke, research partially supported by NSF Grant No. MPS75-09443.