Semiring and Semimodule Issues in MV-Algebras

It is known that an atomic right LCM domain need not be a UFD but is a projectivity-UFD if it is also modular. This paper studies a slightly weaker and easier condition, the RAMP (acronym for the property in the title) , which also ensures that an atomic right LCM domain will be a projectivity-UFD. Among other things it is shown that in an atomic LCM domain, modularity is equivalent to the pair RAMP and LAMP (the left-right analog of RAMP). This result is then used to show that an atomic LCM domain with conjugation is modular. An example is given of an atomic LCM domain that has neither the RAMP nor the LAMP. All rings are not-necessarily commutative integral domains. Recall that an atomic ring is one in which every nonzero nonunit is a product of atoms (i.e. irreducibles) . A ring R is a right LCM domain if for any two elements a and b in R, aR ∩ bR is a principal right ideal. A right LCM domain need not be a left LCM domain [3] . If a ring has both properties it is called an LCM domain. It Is known (see Example 2 below) that, unlike the commutative case, an atomic right LCM domain need not be a UFD (unique factorization domain). In [1] it is shown that if the ring is also modular then it is a projectivity-UFD (definition of the latter recalled below)     

The three-in-a-tree problem

We show that there is a polynomial time algorithm that, given three vertices of a graph, tests whether there is an induced subgraph that is a tree, containing the three vertices. (Indeed, there is an explicit construction of the cases when there is no such tree.) As a consequence, we show that there is a polynomial time algorithm to test whether a graph contains a “theta” as an induced subgraph (this was an open question of interest) and an alternative way to test whether a graph contains a “pyramid” (a fundamental step in checking whether a graph is perfect).     

Outerplanar Thrackles

We show that a graph drawing is an outerplanar thrackle if and only if, up to an inversion in the plane, it is Reidemeister equivalent to an odd musquash. This establishes Conway’s thrackle conjecture for outerplanar thrackles. We also extend this result in two directions. First, we show that no pair of vertices of an outerplanar thrackle can be joined by an edge in such a way that the resulting graph drawing is a thrackle. Secondly, we introduce the notion of crossing rank; drawings with crossing rank 0 are generalizations of outerplanar drawings. We show that all thrackles of crossing rank 0 are outerplanar. We also introduce the notion of an alternating cycle drawing, and we show that a thrackled cycle is alternating if and only if it is outerplanar.     

Stochastic scheduling in an in-forest

Consider a problem of scheduling activities of a research and development project, where precedence relations of the activities constituting the project are represented by edges of an in-forest. Each activity is characterized by two parameters: a cost for attempting that activity and a probability that attempting the activity will lead to successful completion. The problem is to find a policy for attempting activities that minimizes the expected cost incurred until termination (successful completion of the project or the first activity failure). The main result of the paper is the design of an efficient algorithm to determine an optimal sequence in which to attempt the activities; a result which is established for linear and exponential utility functions. It is also shown that, unlike the related problem with out-forest precedence relations, there need not exist an optimal policy that is based on an index-rule for determining priority of edges by evaluating their successors.     

非SM-群的一类rp~3-阶群

称有限群的不可约特征标x为SM-特征标,如果x可由某个次正规子群的线性特征标诱导得到.称有限群为SM-群,如果有限群的所有不可约特征标均为SM-特征标.通过一个例子,将说明rp~3-阶群不一定是SM-群.     

The Turaev genus of an adequate knot

The Turaev genus of a knot is an obstruction to the knot being alternating. An adequate knot is a generalization of an alternating knot. A natural problem is a characterization of the Turaev genus of an adequate knot. In this paper, we show that the Turaev genus of an adequate knot is realized by the genus of the Turaev surface associated to an adequate diagram of the knot using the Khovanov homology. As a result, we obtain the additivity of the Turaev genus of adequate knots, and show that the Turaev genus of an adequate knot is “often” preserved under mutation. We also show that an n-semi-alternating knot is of Turaev genus n. This is the first examples of adequate knots of Turaev genus two or more.     

Optimality equations and inequalities in a class of risk-sensitive average cost Markov decision chains

This note concerns controlled Markov chains on a denumerable sate space. The performance of a control policy is measured by the risk-sensitive average criterion, and it is assumed that (a) the simultaneous Doeblin condition holds, and (b) the system is communicating under the action of each stationary policy. If the cost function is bounded below, it is established that the optimal average cost is characterized by an optimality inequality, and it is to shown that, even for bounded costs, such an inequality may be strict at every state. Also, for a nonnegative cost function with compact support, the existence an uniqueness of bounded solutions of the optimality equation is proved, and an example is provided to show that such a conclusion generally fails when the cost is negative at some state.     

An Equivalence Theorem on Minimum Sheltering Speed for Non-convex Habitats

The paper is devoted to a new family of variational problems for differential inclusions, motivated by the protection of human and wildlife habitats when an invasive environmental disaster occurs. Indeed, the mathematical model consists of a differential inclusion describing the expansion of invaded region over time, and an artificial barrier that cannot be penetrated by the invasive agent is erected to shield the habitat, which serves as the control strategy and is characterized as a one-dimensional rectifiable set. We consider an isotropic case that the disaster spreads with uniform speed in all directions, and develop an equivalence result on the minimum construction speed required for implementing a sheltering strategy determined by a rectifiable Jordan curve. By measuring the invaded portion of barriers over time, it is shown that each connected non-convex habitat admits an equivalent habitat that contains the given habitat and their minimum speeds are equal. In particular, the boundary of an equivalent habitat can be partitioned into two arcs: an arc is locally convex, and the other is part of the boundary of illuminated area. This leads to a corollary on the existence of admissible sheltering strategies for non-convex habitats.     

Relations Between Algebras and Their Subalgebras of Invariants

We prove that, if H is a finite-dimensional semisimple Hopf algebra, and A is an FCR H-module algebra over an algebraically closed field, then A is a PI-algebra, provided the subalgebra of invariants is a PI-algebra. We also show that if A is an affine algebra with an action of a finite group G by automorphisms, the subalgebra of the fixed points A^G is in the center of A, and the characteristic of the ground field is either zero or relatively prime to the order of G, then A^G is affine. Analogous results are proved for graded algebras and H-module algebras over a semisimple triangular Hopf algebra over a field of characteristic zero. We prove also that, if A is an H-module algebra with an identity element, and H is either a semisimple group algebra or its dual, then, if A is semiprimitive (semiprime), then so is A^H.     

Ovoids in finite uniform linear spaces

The concept of an ovoid is extended to linear spaces, and it is shown that a finite uniform linear space with an ovoid is either a trivial structure on a finite set, or else either two or three dimensional. In the three dimensional case, the ovoid is directly related to an inversive plane, in much the same way that an ovoid in a finite projective space is.Dedicated to Professor Tallini on the occasion of his 60th birthday     

Maximal and Minimal Semilattices on Ordered Sets

The map which takes an element of an ordered set to its principal ideal is a natural embedding of that ordered set into its powerset, a semilattice. If attention is restricted to all finite intersections of the principal ideals of the original ordered set, then an embedding into a much smaller semilattice is obtained. In this paper the question is answered of when this construction is, in a certain arrow-theoretic sense, minimal. Specifically, a characterisation is given, in terms of ideals and filters, of those ordered sets which admit a so-called minimal embedding into a semilattice. Similarly, a candidate maximal semilattice on an ordered set can be constructed from the principal filters of its elements. A characterisation of those ordered sets that extend to a maximal semilattice is given. Finally, the notion of a free semilattice on an ordered set is given, and it is shown that the candidate maximal semilattice in the embedding-theoretic sense is the free object.     

An automorphism group of an ω‐stable structure that is not locally (OB)

We observe that there is an example of an automorphism group of a model of an ω‐stable theory—in fact, the prime model of an uncountably categorical theory—that is not locally (OB), answering a question of Rosendal.     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

Extremal Valued Fields

It is shown that every finite-dimensional skew field whose center is an extremal valued field is defect free. We construct an example of an algebraically complete valued field such that a finite-dimensional skew field over it has a non-trivial defect, that is, there exist algebraically complete valued fields that are not extremal.     

Induction of M-convex functions by linking systems

Induction (or transformation) by bipartite graphs is one of the most important operations on matroids, and it is well known that the induction of a matroid by a bipartite graph is again a matroid. As an abstract form of this fact, the induction of a matroid by a linking system is known to be a matroid.M-convex functions are quantitative extensions of matroidal structures, and they are known as discrete convex functions. As with matroids, it is known that the induction of an M-convex function by networks generates an M-convex function. As an abstract form of this fact, this paper shows that the induction of an M-convex function by linking systems generates an M-convex function. Furthermore, we show that this result also holds for M-convex functions on constant-parity jump systems. Previously known operations such as aggregation, splitting, and induction by networks can be understood as special cases of this construction.     

Optimal boundedness criteria for extended-real-valued functions

The notion of genuinely bounded below function is introduced and characterized by means of the concept of co-equilibrated function. As an application, we state two boundedness criteria for extended-real-valued functions, both optimal in a clearly defined sense. The first one says that an extended-real-valued function minorized by an affine map and coinciding from some value up with a co-equilibrated function is bounded below. The second criterion states that an extended-real-valued function minorized by an affine map is bounded below provided that one of its sub-level sets is co-equilibrated.     

Automorphism group and dimension of ordered sets

It is shown that a finite groupG is isomorphic to the automorphism group of a two-dimensional ordered set if and only if it is a generalized wreath product of symmetric groups over an ordered index set that is a dual tree. Furthermore, every finite abelian group is isomorphic to the full automorphism group of a three-dimensional ordered set. Also every finite group is isomorphic to the automorphism group of an ordered set that does not contain an induced crown with more than four elements.     

序半群序同余的一个注记

序半群S的什么子集可以作为S的同余类是一个重要的问题. 在文[8]中,作者证明了如果序半群S的 理想$C$是$S$的某个同余类, 则$C$是凸的; 而且当$C$是强凸理想时，逆命题成立. 在本文中, 我们给出了序半群同余的一个新的构造，并证明了序半群$S$的理想$B$是$S$的某个同余类的充要条件是$B$是凸的.     

On the interaction of deep water waves and exponential shear currents

A train of periodic deep-water waves propagating on a steady shear current with a vertical distribution of vorticity is investigated by an analytic method, namely the homotopy analysis method (HAM). The magnitude of the vorticity varies exponentially with the magnitude of the stream function, while remaining constant on a particular streamline. The so-called Dubreil–Jacotin transformation is used to transfer the original exponentially nonlinear boundary-value problem in an unknown domain into an algebraically nonlinear boundary-value problem in a known domain. Convergent series solutions are obtained not only for small amplitude water waves on a weak current but also for large amplitude waves on a strong current. The nonlinear wave-current interaction is studied in detail. It is found that an aiding shear current tends to enlarge the wave phase speed, sharpen the wave crest, but shorten the maximum wave height, while an opposing shear current has the opposite effect. Besides, the amplitude of waves and fluid velocity decay over the depth more quickly on an aiding shear current but more slowly on an opposing shear current than that of waves on still water. Furthermore, it is found that Stokes criteria of wave breaking is still valid for waves on a shear current: a train of propagating waves on a shear current breaks as the fiuid velocity at crest equals the wave phase speed. Especially, it is found that the highest waves on an opposing shear current are even higher and steeper than that of waves on still water. Mathematically, this analytic method is rather general in principle and can be employed to solve many types of nonlinear partial differential equations with variable coefficients in science, finance and engineering.     

Pricing and lot-sizing for a deteriorating item in a periodic review inventory system with shortages

We consider a single product that is, subject to continuous decay, a multivariate demand function of price and time, shortages allowed and completely backlogged in a periodic review inventory system in which the selling price is allowed to adjust upward or downward periodically. The objective of this paper is to determine the periodic selling price and lot-size over multiperiod planning horizon so that the total discount profit is maximized. The proposed model can be used as an add-in optimizer like an advanced planning system in an enterprise resource planning system that coordinates distinct functions within a firm. Particular attention is placed on investigating the effect of periodic pricing jointly with shortages on the total discount profit. The problem is formulated as a bivariate optimization model solved by dynamic programming techniques coupled with an iterative search process. An intensive numerical study shows that the periodic pricing is superior to the fixed pricing in profit maximization. It also clarifies that shortages strategy can be an effective cost control mechanism for managing deterioration inventory.