A complete set of numerical invariants for a subfactor

We show that certain numerical invariants associated naturally to a subfactor planar algebra constitute a complete family in the sense of determining the isomorphism class of the subfactor planar algebra.In the course of the proof, we show also that planar algebra isomorphisms of subfactor planar algebras can always be chosen to be ∗-preserving. This latter statement generalises the fact that ‘Hopf algebra isomorphisms of finite-dimensional Kac algebras can be chosen to be ∗-preserving’.     

A noncontextualist account of contextualist linguistic data

The paper takes as its starting point the observation that people can be led to retract knowledge claims when presented with previously ignored error possibilities, but offers a noncontextualist explanation of the data. Fallibilist epistemologies are committed to the existence of two kinds of Kp-falsifying contingencies: (i) Non-Ignorable contingencies [NI-contingencies] and (ii) Properly-Ignorable contingencies [PI-contingencies]. For S to know that p, S must be in an epistemic position to rule out all NI-contingencies, but she need not be able to rule out the PI-contingencies. What is required vis-à-vis PI-contingencies is that they all be false. In mentioning PI-contingencies, an interlocutor can lead S mistakenly to think that these contingencies are NI-contingencies, when in fact they are not. Since S cannot rule out these newly mentioned contingencies and since she mistakenly takes them to be NI-contingencies, it is quite natural that she retract her earlier knowledge claim. In short, mentioning NI-contingencies creates a distortion effect. It makes S think that the standards for knowledge are higher than they actually are, which in turn explains why she mistakenly thinks she lacks knowledge. Conclusion: The primary linguistic data offered in support of contextualism can be explained without resorting to contextualism.     

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.     

Free and non-free subgroups of the fundamental group of the Hawaiian Earrings

The space which is composed by embedding countably many circles in such a way into the plane that their radii are given by a null-sequence and that they all have a common tangent point is called “The Hawaiian Earrings”. The fundamental group of this space is known to be a subgroup of the inverse limit of the finitely generated free groups, and it is known to be not free. Within the recent move of trying to get hands on the algebraic invariants of non-tame (e.g. non-triangulable) spaces this space usually serves as the simplest example in this context. This paper contributes to understanding this group and corresponding phenomena by pointing out that several subgroups that are constructed according to similar schemes partially turn out to be free and not to be free. Amongst them is a countable non-free subgroup, and an uncountable free subgroup that is not contained in two other free subgroups that have recently been found. This group, although free, contains infinitely huge “virtual powers”, i.e. elements of the fundamental group of that kind that are usually used in proofs that this fundamental group is not free, and, although this group contains all homotopy classes of paths that are associated with a single loop of the Hawaiian Earrings, this system of ‘natural generators’ can be proven to be not contained in any free basis of this free group.     

Intelligibility and intensionality

A common argumentative strategy employed by anti-reductionists involves claiming that one kind of entity cannot be identified with or reduced to a second because what can intelligibly be predicated of one cannot be predicated intelligibly of the other. For instance, it might be argued that mind and brain are not identical because it makes sense to say that minds are rational but it does not make sense to say that brains are rational. The scope and power of this kind of argument — if valid — are obvious; but if it turns out that ‘It makes sense to say that...’ creates an opaque context, such arguments will fail. I analyze a possible counterexample to validity and show that it is not conclusive, as it depends on what syntactical construction is given to the premises. This leads to the general observation that the argument form under consideration works for some constructions but not others, and thus to the conclusion that further analysis of intelligibility is called for before it can be known whether the argumentative strategy is open to the anti-reductionist or not.     

The degree of maps of free G-manifolds and the average

Suppose that G is a compact Lie group, M and N are orientable, free G-manifolds and f : M → N is an equivariant map. We show that the degree of f satisfies a formula involving data given by the classifying maps of the orbit spaces M/G and N/G. In particular, if the generator of the top dimensional cohomology of M/G with integer coefficients is in the image of the cohomology map induced by the classifying map for M, then the degree is one. The condition that the map be equivariant can be relaxed: it is enough to require that it be “nearly equivariant”, up to a positive constant. We will also discuss the G-average construction and show that the requirement that the map be equivariant can be replaced by a somewhat weaker condition involving the average of the map. These results are applied to maps into real, complex and quaternionic Stiefel manifolds. In particular, we show that a nearly equivariant map of a complex or quaternionic Stiefel manifold into itself has degree one. Dedicated to the memory of Jean Leray     

Sets on which several measures agree

It is known that, given n non-atomic probability measures on the space I = [0, 1], and a number α between 0 and 1, there exists a subset K of I that has measure α in each measure. It is proved here that K may be chosen to be a union of at most n intervals. If the underlying space is the circle S¹ instead of I, then K may be chosen to be a union of at most n ? 1 intervals. These results are shown to be best possible for all irrational and many rational values of α. However, there remain many rational values of α for which we are unable to determine the minimum number of intervals that will suffice.     

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.     

Spectral norms on valued fields

Let be a perfect valued field, be an algebraic closure of be an extension of to and be the G-spectral norm on Let be an algebraic extension of K and be the completion of L relative to We associate to any element a real number and prove that if for all x in , then and is a zero-dimensional regular ring. We show that and prove that is algebraic over (with some additional conditions on K and L). We give a Galois type correspondence between the set of all closed K-subalgebras of and the subfields of L. We prove that is an algebraic closed and zero-dimensional regular ring. Received: 3 March 1999; in final form: 21 February 2000 / Published online: 4 May 2001     

Klarner systems and tiling boxes with polyominoes

Let T be a protoset of d-dimensional polyominoes. Which boxes (rectangular parallelepipeds) can be tiled by T? A nice result of Klarner and Göbel asserts that the answer to this question can always be given in a particularly simple form, namely, by giving a finite list of “prime” boxes. All other boxes that can be tiled can be deduced from these prime boxes. We give a new, simpler proof of this fundamental result. We also show that there is no upper bound to the number of prime boxes, even when restricting attention to singleton protosets. In the last section, we determine the set of prime rectangles for several small polyominoes.     

Analytic smoothing of geometric maps with applications to KAM theory

We show that finitely differentiable diffeomorphisms which are either symplectic, volume-preserving, or contact can be approximated with analytic diffeomorphisms that are, respectively, symplectic, volume-preserving or contact. We prove that the approximating functions are uniformly bounded on some complex domains and that the rate of convergence, in Cr-norms, of the approximation can be estimated in terms of the size of such complex domains and the order of differentiability of the approximated function. As an application to this result, we give a proof of the existence, the local uniqueness and the bootstrap of regularity of KAM tori for finitely differentiable symplectic maps. The symplectic maps considered here are not assumed either to be written in action-angle variables or to be perturbations of integrable systems. Our main assumption is the existence of a finitely differentiable parameterization of a maximal dimensional torus that satisfies a non-degeneracy condition and that is approximately invariant. The symplectic, volume-preserving and contact forms are assumed to be analytic.     

On the Embedding of Ordered Semigroups into Ordered Group

It was shown in [7] that any right reversible, cancellative ordered semigroup can be embedded into an ordered group and as a consequence, it was shown that a commutative ordered semigroup can be embedded into an ordered group if and only if it is cancellative. In this paper we introduce the concept of L-maher and R-maher semigroups and use a technique similar to that used in [7] to show that any left reversible cancellative ordered L or R-maher semigroup can be embedded into an ordered group.     

Complexity in Complex Analysis

We show that the classical kernel and domain functions associated to an n-connected domain in the plane are all given by rational combinations of three or fewer holomorphic functions of one complex variable. We characterize those domains for which the classical functions are given by rational combinations of only two or fewer functions of one complex variable. Such domains turn out to have the property that their classical domain functions all extend to be meromorphic functions on a compact Riemann surface, and this condition will be shown to be equivalent to the condition that an Ahlfors map and its derivative are algebraically dependent. We also show how many of these results can be generalized to finite Riemann surfaces.     

On the convergence of a class of derivative-free minimization algorithms

A convergence analysis is presented for a general class of derivative-free algorithms for minimizing a functionf(x) for which the analytic form of the gradient and the Hessian is impractical to obtain. The class of algorithms accepts finite-difference approximation to the gradient, with stepsizes chosen in such a way that the length of the stepsize must meet two conditions involving the previous stepsize and the distance from the last estimate of the solution to the current estimate. The algorithms also maintain an approximation to the second-derivative matrix and require that the change inx made at each iteration be subject to a bound that is also revised automatically. The convergence theorems have the features that the starting pointx ¹ need not be close to the true solution andf(x) need not be convex. Furthermore, despite the fact that the second-derivative approximation may not converge to the true Hessian at the solution, the rate of convergence is still Q-superlinear. The theorry is also shown to be applicable to a modification of Powell's dog-leg algorithm.     

A tree search procedure for the container pre-marshalling problem

In the container pre-marshalling problem (CPMP) n items are given that belong to G different item groups (g = 1, … , G) and that are piled up in up to S stacks with a maximum stack height H. A move can shift one item from one stack to another one. A sequence of moves of minimum length has to be determined that transforms the initial item distribution so that in each of the stacks the items are sorted by their group index g in descending order. The CPMP occurs frequently in container terminals of seaports. It has to be solved when export containers, piled up in stacks, are sorted in a pre-marshalling process so that they can be loaded afterwards onto a ship faster and more efficiently. This article presents a heuristic tree search procedure for the CPMP. The procedure is compared to solution approaches for the CPMP that were published so far and turns out to be very competitive. Moreover, computational results for new and difficult CPMP instances are presented.     

The path relation for directed planar graphs in rectangles, and its relation to the free diad

In this paper, we define the path relation of a directed graph to be the relation which relates two vertices if there is a path from the first to the second. We study the restriction of this relation to paths from sources to sinks, and consider the question of when two finite graphs embedded in a rectangle give the same relation. We find a set of local changes to these graphs which can be used to get between any two graphs for which this relation is the same. Furthermore, we classify the relations which can arise as this relation for a finite directed graph embedded in a rectangle as the triconvex relations between finite ordinals (defined in this paper).This work originated from some of the author’s work on category theory. It turns out that the category of finite ordinals and relations that can be the path relation of a directed graph embedded in a rectangle, is relevant to the study of diads—introduced by the author as a common generalisation of monads and comonads (note that the terms diad and dyad have been used to mean different things by other authors). More specifically, the referee of one of the author’s papers suggested that it would be useful to identify the category which plays the role for diads that the category of finite ordinals and order-preserving functions plays for monads. It turns out that the category of finite ordinals and relations that can be path relations of graphs embedded in a rectangle, is exactly the category that plays this role.     

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.     

Solution of nonlinear optimal control problems in Hilbert spaces by means of linear programming techniques

Optimal control problems in Hilbert spaces are considered in a measure-theoretical framework. Instead of minimizing a functional defined on a class of admissible trajectory-control pairs, we minimize one defined on a set of measures; this set is defined by the boundary conditions and the differential equation of the problem. The new problem is an infinite-dimensionallinear programming problem; it is shown that it is possible to approximate its solution by that of a finite-dimensional linear program of sufficiently high dimensions, while this solution itself can be approximated by a trajectory-control pair. This pair may not be strictly admissible; if the dimensionality of the finite-dimensional linear program and the accuracy of the computations are high enough, the conditions of admissibility can be said to be satisfied up to any given accuracy. The value given by this pair to the functional measuring the performance criterion can be about equal to theglobal infimum associated with the classical problem, or it may be less than this number. It appears that this method may become a useful technique for the computation of optimal controls, provided the approximations involved are acceptable.     

Efficient Intensional Implementation for Lazy Functional Languages

The intensional transformation is a technique that can be used in order to eliminate higher-order functions from a functional program by introducing appropriate context-manipulation operators. The transformation can be applied to a significant class of higher-order programs and results in equivalent zero-order intensional programs that can be executed in a simple demand-driven way. Despite its simplicity, the transformation has never been seriously evaluated with respect to its efficiency and potential. Certain simple implementations of the technique have been performed, but questions regarding the merits of the method have remained inconclusive. In this paper we demonstrate that the transformation can be efficiently implemented by using what we call lazy activation records, namely activation records in which some entries are filled on-demand. An evaluation of our implementation demonstrates that the technique outperforms some of the most well-known functional programming systems, for the class of programs that can be transformed. This work has been partially supported by the University of Athens under the project “Kapodistrias” (grant no. 70/4/5827).     

Second-order cover inequalities

We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0–1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and –1. We provide an algorithm that generates all non-dominated second-order cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives. Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities that limit sums over disjoint subsets of variables to be at most one.