Optimization of multiple covering of a bounded set with circles

Numerical algorithms for the optimization of multiple covering of a bounded set G in the plane P with equal circles are proposed. The variants in which G is a connected bounded set in P or a finite set in P are considered. The circles may be centered at arbitrary points of G or at points belonging to a given set. Minimization of the radius of the given number of circles and minimization of the number of circles of a given radius are considered. Models and solution algorithms are described, and estimates of the solutions provided by most variants are given. Numerical results are presented.     

Solvability,controllability, and observability of singular systems

The problems of solvability, controllability, and observability for the singular systemKx(t)=Ax(t)+Bu(t) are studied, whereK is a singular, square matrix andu(t) is a complex vector function sufficiently differentiable. The classical theories of matrix pencils are first related to the solvability of singular systems. Then, the concepts of reachability, controllability, and observability of regular systems are extended to singular systems. Finally, the set of reachable states is described. The proposed matrix conditions for testing the controllability and observability of singular systems are simple and always feasible.     

Strong Asymmetric Digraphs with Prescribed Interior and Annulus

The directed distance d(u,v) from u to v in a strong digraph D is the length of a shortest u-v path in D. The eccentricity e(v) of a vertex v in D is the directed distance from v to a vertex furthest from v in D. The center and periphery of a strong digraph are two well known subdigraphs induced by those vertices of minimum and maximum eccentricities, respectively. We introduce the interior and annulus of a digraph which are two induced subdigraphs involving the remaining vertices. Several results concerning the interior and annulus of a digraph are presented.     

Plactic algebra of rank 3

The structure of the algebra K[M] of the plactic monoid M of rank 3 over a field K is studied. The minimal prime ideals of K[M] are described. There are only two such ideals and each of them is a principal ideal determined by a homogeneous congruence on M. Moreover, in case K is uncountable and algebraically closed, the left and right primitive spectrum and the corresponding irreducible representations of the algebra K[M] are described. All these representations are monomial. As an application, a new proof of the semiprimitivity of K[M] is given.     

On the Structures of the Milnor K-Groups of Some Complete Discrete Valuation Fields

For a complete discrete valuation field K, the unit group of K has a natural decreasing filtration with respect to the valuation, and the graded quotients of this filtration are written in terms of the residue field. The Milnor K-group of a field is a generalization of the unit group. The Milnor K-group of K has a natural decreasing filtration of the same kind. However, if K is of mixed characteristics and has an absolute ramification index greater than one, the structure is not yet known. The aim of this paper is to determine the structure of the Milnor K-group of some special K, which are of mixed characteristics (0,p), whose residue fields are allowed to be imperfect, and which are of absolute ramification index p(p–1).     

q-Trigonal Klein surfaces

In this paperq-trigonal Klein surfaces are introduced in a similar way to that ofq-hyperelliptic surfaces. They are characterized by means of non-Euclidean crystallographic groups (NEC groups in short). As a consequence of this characterization, given a family of Klein surfaces (orientable or not) with topological genusg andk boundary components the admissible values forq are calculated. In particular, the families for which there is no admissibleq or families with uniqueq are obtained. The authors are partially supported by DGICYT PB98 0017.     

On derivations of the heisenberg algebra

Derivations of the Heisenberg algebraH and some related questions are studied. The ideas and the language of formal differential geometry are used. It is proved that all derivations of this algebra are inner. The main subalgebras of the Lie algebraD(H) of all derivations ofH are distinguished, and their properties are studied. It is shown that the algebraH interpreted as a Lie algebra (with the commutator as the Lie bracket) forms a one-dimensional central extension ofD(H). Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 118. No. 2 pp. 163–189, February, 1999.     

Basic Hopf algebras and quantum groups

This paper investigates the structure of basic finite dimensional Hopf algebras H over an algebraically closed field k. The algebra H is basic provided H modulo its Jacobson radical is a product of the field k. In this case H is isomorphic to a path algebra given by a finite quiver with relations. Necessary conditions on the quiver and on the coalgebra structure are found. In particular, it is shown that only the quivers given in terms of a finite group G and sequence of elements of G in the following way can occur. The quiver has vertices and arrows , where the set is closed under conjugation with elements in G and for each g in G, the sequences W and are the same up to a permutation. We show how is a kG-bimodule and study properties of the left and right actions of G on the path algebra. Furthermore, it is shown that the conditions we find can be used to give the path algebras themselves a Hopf algebra structure (for an arbitrary field k). The results are also translated into the language of coverings. Finally, a new class of finite dimensional basic Hopf algebras are constructed over a not necessarily algebraically closed field, most of which are quantum groups. The construction is not characteristic free. All the quivers , where the elements of W generates an abelian subgroup of G, are shown to occur for finite dimensional Hopf algebras. The existence of such algebras is shown by explicit construction. For closely related results of Cibils and Rosso see [Ci-R]. Received August 15, 1994; in final form May 16, 1997     

Projection Method for Cauchy Problem for an Operator-Differential Equation

In the current paper, we study a projection method for a Cauchy problem for an operator-differential equation with a leading self-adjoint operator A(t) and a subordinate linear operator K(t) in a Hilbert space. The projection subspaces are linear spans of eigenvectors of an operator similar to A(t). It is assumed that the operators A(t) and K(t) are sufficiently smooth. Error estimates for the approximate solutions and their derivatives are obtained. The application of the developed method for solving the initial boundary value problems is given.     

Cluster-concealed algebras

The cluster-tilted algebras have been introduced by Buan, Marsh and Reiten, they are the endomorphism rings of cluster-tilting objects T in cluster categories; we call such an algebra cluster-concealed in case T is obtained from a preprojective tilting module. For example, all representation-finite cluster-tilted algebras are cluster-concealed. If C is a representation-finite cluster-tilted algebra, then the indecomposable C-modules are shown to be determined by their dimension vectors. For a general cluster-tilted algebra C, we are going to describe the dimension vectors of the indecomposable C-modules in terms of the root system of a quadratic form. The roots may have both positive and negative coordinates and we have to take absolute values.     

Componentwise perturbation analyses for the QR factorization

Summary. This paper gives componentwise perturbation analyses for Q and R in the QR factorization A=QR, , R upper triangular, for a given real $m\times n$ matrix A of rank n. Such specific analyses are important for example when the columns of A are badly scaled. First order perturbation bounds are given for both Q and R. The analyses more accurately reflect the sensitivity of the problem than previous such results. The condition number for R is bounded for a fixed n when the standard column pivoting strategy is used. This strategy also tends to improve the condition of Q, so usually the computed Q and R will both have higher accuracy when we use the standard column pivoting strategy. Practical condition estimators are derived. The assumptions on the form of the perturbation are explained and extended. Weaker rigorous bounds are also given. Received April 11, 1999 / Published online October 16, 2000     

On the Spectra of Certain Graphs Arising from Finite Fields

Cayley graphs on a subgroup ofGL(3,p),p>3 a prime, are defined and their properties, particularly their spectra, studied. It is shown that these graphs are connected, vertex-transitive, nonbipartite, and regular, and their degrees are computed. The eigenvalues of the corresponding adjacency matrices depend on the representations of the group of vertices. The “1-dimensional” eigenvalues can be completely described, while a portion of the “higher dimensional” eigenfunctions are discrete analogs of Bessel functions. A particular subset of these graphs is conjectured to be Ramanujan and this is verified for over 2000 graphs. These graphs follow a construction used by Terras on a subgroup ofGL(2,p). This method can be extended further to construct graphs using a subgroup ofGL(n, p) forn≥4. The 1-dimensional eigenvalues in this case can be expressed in terms of the 1-dimensional eigenvalues of graphs fromGL(2,p) andGL(3,p); this part of the spectra alone is sufficient to show that forn≥4, the graphs fromGL(n, p) are not in general Ramanujan.     

Matrix transformations of summability domains of generalized matrix methods in Banach spaces

The necessary and sufficient conditions for a matrix M to be a transform from the summability domain of generalized matrix method A into the summability domain of another generalized matrix method B are proved. The elements of Mare continuous linear operators from a Banach space X into another Banach space Y, and the elements of A and B are continuous linear operators from X into X and from Y into Y, respectively. As a special case there are considered the case when A is the generalized Riesz method.     

Surrogate methods for linear inequalities

Three algorithms are developed and validated for finding a pointx inR ⁿ that satisfies a given system of inequalities,Axb. A andb are a given matrix and a given vector inR ^m×n andR ^m , respectively, with the rows ofA assumed normalized. The algorithms are iterative and are based upon the orthogonal projection of an infeasible point onto the manifold of the bounding hyperplanes of some of the given constraints. The choice of the active constraints and the actual projection are accomplished through the use of surrogate constraints.This work was supported in part by the City University of New York Research Center. The author thanks Professor D. Goldfarb for suggesting the problem and also for his valuable literature information and time. The word surrogate was borrowed from one of his works.     

Finite groups in which all p-subnormal subgroups form a lattice

O. Kegel, in 1962, introduced the concept of p-subnormal subgroups of a finite group as the subgroups whose intersections with all Sylow p-subgroups of the group are Sylow p-subgroups of the subgroup. The set of p-subnormal subgroup of a finite group is not a lattice in general. In this paper, the class of all finite groups in which all p-subnormal subgroups from a lattice is determined. This is the class of all finite p-soluble groups whose p-length and p′-length, both, are less or equal to 1. The join-semilattice case and the meet-semilattice case are analyzed separately. The authors are supported by Proyecto PB 94-1048 of DGICYT, Ministerio de Educación y Ciencia of Spain.     

A common generalization of line graphs and clique graphs

Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a k-edge of a graph we mean a complete subgraph with k vertices or a clique with fewer than k vertices. The k-edge graph Δ_k(G) of a graph G is defined as the intersection graph of the set of all k-edges of G. The following three problems are investigated for k-edge graphs. The first is the characterization problem. Second, sets of graphs closed under the k-edge graph operator are found. The third problem is the question of convergence: What happens to a graph if we take iterated k-edge graphs?     

Quotients of partial abelian monoids

A hierarchy of partial abelian structures is considered. In an order of decreasing generality, these structures include partial abelian monoids (PAM), cancellative PAMs (CPAM), effect algebras (or D-posets), orthoalgebras, orthomodular posets (OMP) and orthomodular lattices (OML). If P is a PAM, the concepts of a congruence on P and a quotient P are defined. Similar definitions are given for quotients of higher level categories in the hierarchy. The notion of a Riesz ideal I on a CPAM P is defined and it is shown that I generates a congruence on P. The corresponding quotients P/I for categories in the hierarchy are studied. It is shown that a subset I of an OML is a Riesz ideal if and only if I is a p-ideal. Moreover, for effect algebras, we show that congruences generated by Riesz ideals are precisely those that are given by a perspectivity. The paper includes a large number of counterexamples and examples that illustrate various concepts. Received April 14, 1997; accepted in final form January 19, 1998.     

Nonlinear deformations of a slender rod rotated at one end

Summary A thin elastic rod is rotated at one end. The nonlinear deformations due to centrifugal forces are studied. The problem is governed by a nondimensional parameterJ which signifies the relative importance of rotation to flexibility, and the angle a between the rotation axis and the clamped end. The nonlinear differential equations are solved by three different perturbations and also numerical integration for the rangeJ5. Force, moment and displacement characteristics are determined. The solutions are unique for smallJ. Three solutions are possible, one may be unstable, for largerJ. Catastrophic changes may occur whenJ is decreased.     

Orthogonal latin square graphs

An orthogonal latin square graph (OLSG) is one in which the vertices are latin squares of the same order and on the same symbols, and two vertices are adjacent if and only if the latin squares are orthogonal. If G is an arbitrary finite graph, we say that G is realizable as an OLSG if there is an OLSG isomorphic to G. The spectrum of G [Spec(G)] is defined as the set of all integers n that there is a realization of G by latin squares of order n. The two basic theorems proved here are (1) every graph is realizable and (2) for any graph G, Spec G contains all but a finite set of integers. A number of examples are given that point to a number of wide open questions. An example of such a question is how to classify the graphs for which a given n lies in the spectrum.     

Convergence of two-dimensional branching recursions

The asymptotic distribution of branching type recursions (L_n) of the form is investigated in the two-dimensional case. Here is an independent copy of L_n−1 and A,B are random matrices jointly independent of . The asymptotics of L_n after normalization are derived by a contraction method. The limiting distribution is characterized by a fixed point equation. The assumptions of the convergence theorem are checked in some examples using eigenvalue decompositions and computer algebra.