Bruck–Reilly extensions of direct products of monoids and completely (0-)simple semigroups

We say that a class of monoids satisfies the property ℘ if every monoid in that class that admits a finitely presented Bruck–Reilly extension is finitely generated. We show that completely (0-)simple semigroups satisfy ℘, and that the direct product of two monoids in a class that satisfy ℘ also satisfies ℘ subject to a certain condition on the endomorphisms of the direct product. As a consequence of this result we obtain a new class of bands and a new class of completely regular semigroups that satisfy property ℘.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

Illusory possibilities and imagining counterparts

Given Kripke’s semantic views, a statement, such as ‘Water is H₂O’, expresses a necessary a posteriori truth. Yet it seems that we can conceive that this statement could have been false; hence, it appears that we can conceive impossible states of affairs as holding. Kripke used a de dicto strategy and a de re strategy to address three illusions that arise with respect to necessary a posteriori truths: (1) the illusion that a statement such as ‘Water is H₂O’ possibly expresses a falsehood, (2) the illusion that conceivability can fail to latch on to a genuine metaphysical possibility, and (3) the illusion that one can access a real metaphysical possibility by conceiving that water is not H₂O. In this paper I argue that while Kripke’s de dicto strategy dispels (1), his strategies do not enable him to dispel (2) and (3).     

Little Grothendieck`s theorem for real JB*-triples

We prove that given a real JB*-triple E, and a real Hilbert space H, then the set of those bounded linear operators T from E to H, such that there exists a norm one functional and corresponding pre-Hilbertian semi-norm on E such that for all , is norm dense in the set of all bounded linear operators from E to H. As a tool for the above result, we show that if A is a JB-algebra and is a bounded linear operator then there exists a state such that for all . Received June 28, 1999; in final form January 28, 2000 / Published online March 12, 2001     

Solving discrete systems of nonlinear equations

We study the existence problem of a zero point of a function defined on a finite set of elements of the integer lattice Zⁿ of the n-dimensional Euclidean space Rⁿ. It is assumed that the set is integrally convex, which implies that the convex hull of the set can be subdivided in simplices such that every vertex is an element of Zⁿ and each simplex of the triangulation lies in an n-dimensional cube of size one. With respect to this triangulation we assume that the function satisfies some property that replaces continuity. Under this property and some boundary condition the function has a zero point. To prove this we use a simplicial algorithm that terminates with a zero point within a finite number of iterations. The standard technique of applying a fixed point theorem to a piecewise linear approximation cannot be applied, because the ‘continuity property’ is too weak to assure that a zero point of the piecewise linear approximation induces a zero point of the function itself. We apply the main existence result to prove the existence of a pure Cournot-Nash equilibrium in a Cournot oligopoly model. We further obtain a discrete analogue of the well-known Borsuk-Ulam theorem and a theorem for the existence of a solution for the discrete nonlinear complementarity problem.     

No Lacuna and No Vicious Regress: A Reply to Le Poidevin

In his “Space, supervenience and substantivalism”, Le Poidevin proposes a substantivalism in which space is discrete, implying that there are unmediated spatial relations between neighboring primitive points. This proposition is motivated by his concern that relationism suffers from an explanatory lacuna and that substantivalism gives rise to a vicious regress. Le Poidevin implicitly requires that the relationist be committed to the “only x and y” principle regarding spatial relations. It is not obvious that the relationist is committed to this principle in such a context. An additional motivation for Le Poidevin's argument, that space should be considered to be discrete, is that he believes that substantivalists are committed to a vicious regress. I show that the regress is in fact not of the vicious variety. These two main arguments show that Le Poidevin's suggestion that we drop the density postulate for space is unnecessary.

Epireflections and supercompact cardinals

We prove that the existence of arbitrarily large supercompact cardinals implies that every absolute epireflective class of objects in a balanced accessible category is a small-orthogonality class. In other words, if L is a localization functor on a balanced accessible category such that the unit morphism X→LX is an epimorphism for all X and the class of L-local objects is defined by an absolute formula, then the existence of a sufficiently large supercompact cardinal implies that L is a localization with respect to some set of morphisms.     

Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?

The Miller–Tucker–Zemlin (MTZ) Subtour Elimination Constraints (SECs) and the improved version by Desrochers and Laporte (DL) have been and are still in regular use to model a variety of routing problems. This paper presents a systematic way of deriving inequalities that are more complicated than the MTZ and DL inequalities and that, in a certain way, “generalize” the underlying idea of the original inequalities. We present a polyhedral approach that studies and analyses the convex hull of feasible sets for small dimensions. This approach allows us to generate generalizations of the MTZ and DL inequalities, which are “good” in the sense that they define facets of these small polyhedra. It is well known that DL inequalities imply a subset of Dantzig–Fulkerson–Johnson (DFJ) SECs for two-node subsets. Through the approach presented, we describe a generalization of these inequalities which imply DFJ SECs for three-node subsets and show that generalizations for larger subsets are unlikely to exist. Our study presents a similar analysis with generalizations of MTZ inequalities and their relation with the lifted circuit inequalities for three node subsets.     

On the Circuit-cocircuit Intersection Conjecture

Oxley has conjectured that for k≥4, if a matroid M has a k-element set that is the intersection of a circuit and a cocircuit, then M has a (k−2)-element set that is the intersection of a circuit and a cocircuit. In this paper we prove a stronger version of this conjecture for regular matroids. We also show that the stronger result does not hold for binary matroids. The second author was partially supported by CNPq (grant no 302195/02-5) and the ProNEx/CNPq (grant no 664107/97-4).     

Well-posedness for magnetoviscoelastic fluids in 3D

We show that the system of equations describing a magnetoviscoelastic fluid in three dimensions can be cast as a quasilinear parabolic system. Using the theory of maximal $L_p$-regularity, we establish existence and uniqueness of local strong solutions and we show that each solution is smooth (in fact analytic) in space and time. Moreover, we give a complete characterization of the set of equilibria and show that solutions that start out close to a constant equilibrium exist globally and converge to a (possibly different) constant equilibrium. Finally, we show that every solution that is eventually bounded in the topology of the state space exists globally and converges to the set of equilibria.     

On the structure ofn-point sets

Letn be an integer greater than one. Our main result, called the “Structure Theorem” is that a set that containsn−1 disjoint continua that are cut by a single line cannot be ann-point set, that is, a set that meets every line in preciselyn points. This theorem unifies and significantly improves upon a number of known theorems. The second part of the paper is devoted to several theorems that address the question when a set that meets every line in at mostn points can be extended to ann-point set. These theorems also highlight the sharpness of the Structure Theorem.     

Equicalmness and Epiderivatives That Are Pointwise Limits

Recently, Moussaoui and Seeger (Ref. 1) studied the monotonicity of first-order and second-order difference quotients with primary goal the simplification of epilimits. It is well known that epilimits (lim inf and lim sup) can be written as pointwise limits in the case of a sequence of functions that is equi-lsc. In this paper, we introduce equicalmness as a condition that guarantees equi-lsc, and our primary goal is to give conditions that guarantee that first-order and second-order difference quotients are equicalm. We show that a piecewise-C ¹ function f with convex domain is epidifferentiable at any point of its domain. We also show that a convex piecewise C ²-function (polyhedral pieces) is twice epidifferentiable. We thus obtain a modest extension of the Rockafellar result concerning the epidifferentiability of piecewise linear-quadratic convex functions.     

Products of idempotent matrices over integral domains

We say that a ring R has the idempotent matrices property if every square singular matrix over R is a product of idempotent matrices. It is known that every field, and more generally, every Euclidean domain has the idempotent matrices property. In this paper we show that not every integral domain has the idempotent matrices property and that if a projective free ring has the idempotent matrices property then it must be a Bezout domain. We also show that a principal ideal domain has the idempotent matrices property if and only if every fraction a/b with b≠0 has a finite continued fraction expansion. New proofs are also provided for the results that every field and every Euclidean domain have the idempotent matrices property.     

Fibre products, non-positive curvature, and decision problems

We give a criterion for fibre products to be finitely presented and use it as the basis of a construction that encodes the pathologies of finite group presentations into pairs of groups where G is a product of hyperbolic groups and P is a finitely presented subgroup. This enables us to prove that there is a finitely presented subgroup P in a biautomatic group G such that the generalized word problem for is unsolvable and P has an unsolvable conjugacy problem. An additional construction shows that there exists a compact non-positively curved polyhedron X such that is biautomatic and there is no algorithm to decide isomorphism among the finitely presented subgroups of . Received: October 7, 1999.     

Incidence properties of cosets in loops

We study incidence properties among cosets of infinite loops, with emphasis on well‐structured varieties such as antiautomorphic loops and Bol loops. While cosets in groups are either disjoint or identical, we find that the incidence structure in general loops can be much richer. Every symmetric design, for example, can be realized as a canonical collection of cosets of a infinite loop. We show that in the variety of antiautomorphic loops the poset formed by set inclusion among intersections of left cosets is isomorphic to that formed by right cosets. We present an algorithm that, given a infinite Bol loop S, can in some cases determine whether |S| divides |Q| for all infinite Bol loops Q with S?Q, and even whether there is a selection of left cosets of S that partitions Q. This method results in a positive confirmation of Lagrange's Theorem for Bol loops for a few new cases of subloops. Finally, we show that in a left automorphic Moufang loop Q (in particular, in a commutative Moufang loop Q), two left cosets of S?Qare either disjoint or they intersect in a set whose cardinality equals that of some subloop of S.     

A relationship between two almost f-algebra products

Let A be an uniformly complete almost f-algebra. Then is a positively generated ordered vector subspace of A with as a positive cone. If is a positive linear operator, we put the linear operator defined by with for all is the algebra of all order bounded linear operators of A). Let denote the range of and let's define a new product by putting for all . It is easily checked that if then , this shows that if it happens that the product is associative then A is an almost f- algebra with respect to this new product. It turns out that a necessarily and sufficient condition in order that be an associative product is that is a commutative subalgebra of . We find necessarily and sufficient conditions on T in order that is an almost f-algebra (respect.; d-algebra, f-algebra) product. Such conditions are described in terms of the algebraic and order structure of the algebra .?The converse problem is also studied. More precisely, let A be an uniformly complete almost f-algebra and assume that is another almost f-algebra product on A. The aim is to find sufficient conditions in order that there exist such that for all . It will be showed that a sufficient condition is that A is a d-algebra with respect to the initial product. An example is produced which shows that the condition "A is a d-algebra with respect to the initial product" can not be weakened. Received November 8, 1999; accepted in final form February 14, 2000.     

𝔏-Rickart Modules

It is well known that the Rickart property of rings is not a left-right symmetric property. We extend the notion of the left Rickart property of rings to a general module theoretic setting and define 𝔏-Rickart modules. We study this notion for a right R-module M _R where R is any ring and obtain its basic properties. While it is known that the endomorphism ring of a Rickart module is a right Rickart ring, we show that the endomorphism ring of an 𝔏-Rickart module is not a left Rickart ring in general. If M _R is a finitely generated 𝔏-Rickart module, we prove that End _R (M) is a left Rickart ring. We prove that an 𝔏-Rickart module with no set of infinitely many nonzero orthogonal idempotents in its endomorphism ring is a Baer module. 𝔏-Rickart modules are shown to satisfy a certain kind of nonsingularity which we term “endo-nonsingularity.” Among other results, we prove that M is endo-nonsingular and End _R (M) is a left extending ring iff M is a Baer module and End _R (M) is left cononsingular.     

On the invertibility and bounded extension of C 0 -semigroups

A well-known necessary and sufficient condition for the operator A to be the infinitesimal generator of a strongly continuous (C ₀ -) group is that both A and -A generate a C ₀ -semigroup. This seems to imply that one has to check the conditions in the Hille-Yosida Theorem for both A and -A . In this paper we show that this is not necessary. Given that A generates a C ₀ -semigroup we prove that a (weak) growth bound on the resolvent on a left half plane is sufficient to guarantee that A generates a group. This extends the recent result found by Liu, see [6]. Furthermore, we study when a generator of a bounded C ₀ -semigroup is the generator of a bounded group. The condition that we obtain is the same as found by Van Casteren in [2, 3], but we present a direct proof.     

Transfer and Tate’s theorem

Let H be a subgroup of a finite group G, and assume that p is a prime that does not divide |G : H|. In favorable circumstances, one can use transfer theory to deduce that the largest abelian p-groups that occur as factor groups of G and of H are isomorphic. When this happens, Tate’s theorem guarantees that the largest not-necessarily-abelian p-groups that occur as factor groups of G and H are isomorphic. Known proofs of Tate’s theorem involve cohomology or character theory, but in this paper, a new elementary proof is given. It is also shown that the largest abelian p-factor group of G is always isomorphic to a direct factor of the largest abelian p-factor group of H. Received: 17 June 2008     

The Max-Flow Min-Cut theorem for countable networks

We prove a strong version of the Max-Flow Min-Cut theorem for countable networks, namely that in every such network there exist a flow and a cut that are “orthogonal” to each other, in the sense that the flow saturates the cut and is zero on the reverse cut. If the network does not contain infinite trails then this flow can be chosen to be mundane, i.e. to be a sum of flows along finite paths. We show that in the presence of infinite trails there may be no orthogonal pair of a cut and a mundane flow. We finally show that for locally finite networks there is an orthogonal pair of a cut and a flow that satisfies Kirchhoff's first law also for ends.