Global Optimization Algorithm for the Nonlinear Sum of Ratios Problem

This article presents a branch-and-bound algorithm for globally solving the nonlinear sum of ratios problem (P). The algorithm economizes the required computations by conducting the branch-and-bound search in ^p, rather than in ⁿ, where p is the number of ratios in the objective function of problem (P) and n is the number of decision variables in problem (P). To implement the algorithm, the main computations involve solving a sequence of convex programming problems for which standard algorithms are available.     

Arithmetic and other properties of certain Delphic semigroups. I

Summary Some aspects of Delphic semigroups in general — in particular, the idea of an hereditary subsemigroup, which has many uses in connexion with Delphic semigroups — are first treated. After that, attention is directed to the arithmetic of ⁺, the semigroup of positive renewal sequences. In a Delphic semigroup the aboriginal elements are the simples and the members of I ₀: a class of simples of ⁺ is constructed and the simples are shown to be residual. I ₀ is explicitly identified, and this leads to a canonical factorization of ⁺. The properties of division in ⁺ are discussed.     

Présentations des groupes de Fischer (II)

In this paper we give Coxeter presentation (X, ) for the three Fischer groupsG=Fi₂₂, Fi₂₃, Fi₂₄; we apply methods exposed in the first part. Each of these groups is generated by a class of 3-transpositions (named here a Fischer class) in which elements ofX are chosen. A subset of is the set of all the relations (xy) ^m(x,y)=1, wherex andy are inX and wherem(x,y) means the order ofxy inG. We obtainG as a specified quotient of the Coxeter group (X, ) with the appropriate diagram .     

Présentations des groupes de Fischer (I)

This work gives a method for constructing presentation (X, ) for a group generated by a class of 3-transpositions (named here a Fischer class) in which {ie275-1}(G/Z(G)) is simple and non-abelian. The generating set X is contained in D; is the set of relations (xy) ^m(x,y)=1, x and y in X, where m(x, y) is the order of the product xy in G, m(x, y) 3; is a set of relations between elements of X. The group G is constructed as a quotient of the Coxeter group (X, ).These results are applied to symplectic and orthogonal groups over {ie275-2}. Applications to other groups, in particular to the sporadic Fischer groups, will follow later.     

First order properties of random posets

Let =(n,p) be a binary relation on the set [n]={1, 2, ..., n} such that (i,i) for every i and (i,j) with probability p, independently for each pair i,j [n], where i<j. Define as the transitive closure of and denote poset ([n], ) by R(n, p). We show that for any constant p probability of each first order property of R(n, p) converges as n .     

On Random Sets Connected to the Partial Records of Poisson Point Process

Random intervals are constructed from partial records in a Poisson point process in ]0,[×]0,[. These are used to cover partially [0,[; the purpose of this work is to study the random set that is left uncovered. We show that enjoys the regenerative property and identify its distribution in terms of the characteristics of the Poisson point process. As an application we show that is almost surely a fractal set and we calculate its dimension.     

Discrepancy and approximations for bounded VC-dimension

Let (X, ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in . We show that if for anym-point subset the number of distinct subsets induced by onY is bounded byO(m ^d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n ^1/2–1/2d(logn)^1+1/2d ). Also if any subcollection ofm sets of partitions the points into at mostO(m ^d) classes, then there is a coloring with discrepancy at mostO(n ^1/2–1/2dlogn). These bounds imply improved upper bounds on the size of -approximations for (X, ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.Work of J.M. and E.W. was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 3075 (project ALCOM). L.W. acknowledges support from the Deutsche Forschungsgemeinschaft under grant We 1265/1-3, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

Bruck nets,codes, and characters of loops

Numerous computational examples suggest that if _{k-1 k} are (k- 1)- and k-nets of order n, then rank _{p k} - rank _{p k-1} n - k + 1 for any prime p dividing n at most once. We conjecture that this inequality always holds. Using characters of loops, we verify the conjecture in case k = 3, proving in fact that if p ^e n, then rank _{p 3} 3n - 2 - e, where equality holds if and only if the loop G coordinatizing ₃ has a normal subloop K such that G/K is an elementary abelian group of order p ^e . Furthermore if n is squarefree, then rank _p = 3n - 3 for every prime p ¦ n, if and only if ₃ is cyclic (i.e., ₃ is coordinated by a cyclic group of order n).The validity of our conjectured lower bound would imply that any projective plane of squarefree order, or of order n 2 mod 4, is in fact desarguesian of prime order.     

Some properties of lattices of radical classes of lattice-ordered groups

Aradical class of lattice-ordered groups (-groups) is a class closed under taking convex-subgroups, joins of convex-subgroups, and-isomorphic images. Imposing various other closure conditions leads to many specific types of radical classes (e.g., torsion classes). For several of these types, the complete latticeT of radical classes of that type has been studied, and such latticesT are our object of study here. We give the characteristic properties of closed-kernel radical mappings and polar kernel radical mappings. We prove in many instances thatT isrelatively polarized, that is, for any ], T with ] there exists a unique largest T such that = ], and often we are able to explicitly identify. By using these properties we characterize meet irreducibility in the latticeT of polar kernel radical classes.Presented by M. Henriksen.     

Representations of tensor product l.m.c.*-algebras

If E is a l.m.c.*-algebra with a b.a.i., (E), (E) denote the enveloping algebra and the space of representations of E respectively, while (E) stands for the non-zero extreme points of the continuous positive linear forms on E. Thus, for suitable l.m.c.*-algebras E, F and an admissible topology on E F, (E F) is given by the completed-tensor product of (E), (F) (where is the projective tensorial l.m.c.C*-topology), while (E F) by the cartesian product of (E), (F). An analogous decomposition of (E F) is not valid in general.This paper is partly based on the author's Ph.D. Thesis (Univ. of Athens)     

Commutativity of operators on the lattice of existence varieties

In a previous paper the authors introduced seven complete congruences on the lattice _ev(I of e-varieties of regular semigroups of the form _P :U _P VPU=PV, whereP is drawn from a small set of e-varieties: left zero, right zero, rectangular bands, groups, left groups, right groups and completely simple semigroups. Four new complete congruences are introduced here of the form _P :U _P VPU=PV, whereP is one of the following classes of regular semigroups: left monoids, right monoids, monoids, idempotent generated semigroups. For each complete congruence on _ev(I) and eachU_ev(I), the -class ofU is an interval [U ,U ] so that there is associated with each such congruence an idempotent operatorUU on _ev(I). This paper establishes numerous results concerning the commutativity of operators of this form.This work was supported in part by NSERC Grant 4044.     

A perturbation bound for the generalized polar decomposition

LetA be anm×n complex matrix. A decompositionA=QH is termed ageneralized polar decomposition ofA ifQ is anm×n subunitary matrix (sometimes also called a partial isometry) andH a positive semidefinite Hermitian matrix. It was proved that a nonzero matrixA ^m×n has a unique generalized polar decompositionA=QH with the property (Q ^H )=(H), whereQ ^H denotes the conjugate transpose ofQ and (H) the column space ofH. The main result of this note is a perturbation bound forQ whenA is perturbed.     

Algorithmic aspects of intersection graphs and representation hypergraphs

Let be a family of sets. The intersection graph of is obtained by representing each set in by a vertex and connecting two vertices by an edge if and only if their corresponding sets intersect. Of primary interest are those classes of intersection graphs of families of sets having some specific topological or other structure. The grandfather of all intersection graphs is the class of interval graphs, that is, the intersection graphs of intervals on a line.The scope of research that has been going on in this general area extends from the mathematical and algorithmic properties of intersection graphs, to their generalizations and graph parameters motivated by them. In addition, many real-world applications involve the solution of problems on such graphs.In this paper a number of topics in algorithmic combinatorics which involve intersection graphs and their representative families of sets are presented. Recent applications to computer science are also discussed. The intention of this presentation is to provide an understanding of the main research directions which have been investigated and to suggest possible new directions of research.     

Hyperaffine planes over hyperfields

Summary In this paper we solve the problem of finding suitable conditions for an hyperaffine plane (,) under which a planar hyperfield K exists such that (,) is isomorphic to the hyperaffine plane (K²,').Research partially supported by C.N.R.-G.N.S.A.G.A.     

Bifurcation for a semilinear elliptic equation on ℛN with radially symmetric coefficients

We consider the semilinear eigenvalue problem on ^N (N 2) (N2) and investigate the question under which conditions on the radially symmetric function q, =0 is a bifurcation point for this equation in H¹, In H² and in L^p for 2p+.     

Arithmetic and other properties of certain Delphic semigroups. II

Summary This paper continues [2]. We show that the sets of infinitely divisible elements of the Delphic semigroups ⁺ (of positive renewal sequences) and P (of standard p-functions) are additively convex, and do a Choquet analysis in each case. We draw up the (M, m) diagram for members of , and deduce from it that the product topology on is metrizable. Finally we look at the arithmetic of , showing that the simples are residual in it, and partially identifying I ₀, the set of infinitely divisible elements without simple factors. Many examples are given.I am indebted to Professor D. G. Kendall for his constant help and encouragement in the course of the research leading to this paper and [2].     

Maximal Partial Spreads and Flocks

Denote by a flock of a quadratic cone of PG(3,q) by S() the spread of PG(3,q) associated with and by l the common line of the base reguli. Suppose that there are two lines not transversal to a base regulus which share the same lines of S() Then we prove that is either linear or a Kantor-Knuth semifield flock. Using this property we can extend the result of J3 on derivable flocks proving that, if a set of q + 1 lines of S() defines a derivable net different from a base regulus-net, then is either linear or a Kantor-Knuth semifield flock. Moreover if l is not a component of the derivable net, then is linear.     

A dissipative transformation with a trivial tail-algebra

Summary In [1], an example was given of a measure-preserving dissipative transformation T in a -finite measure space (X, , ), such that T is conservative in the measure space (X, , ) where . Here we shall show that for this transformation we actually have R ={ØX}[].     

Extension of Subgradient Techniques for Nonsmooth Optimization in Banach Spaces

In this paper we continue the study of the subgradient method for nonsmooth convex constrained minimization problems in a uniformly convex and uniformly smooth Banach space. We consider the case when the stepsizes satisfy _{k=1 k} =, lim _{k k} =0.     

Structure of integrable supersymmetric nonlinear dynamical systems on reduced invariant submanifolds

Based on an analysis of a supersymmetric extension of the algebra of pseudodifferential operators on ¹ an infinite hierarchy of supersymmetric Lax-integrable nonlinear dynamical systems is constructed by means of the Yang-Baxter -equation method. The structure of these systems on reduced invariant submanifolds specified by a natural invariant Lax-type spectral problem is investigated.Translated from Ukrayins'kyy Matematychnyy Zhurnal, Vol. 44, No. 9, pp. 1292–1295, September, 1992.