Uniformities with the same Hausdorff hypertopology

Two uniformities U and V on a set X are said to be H-equivalent if their corresponding Hausdorff uniformities on the set of all non-empty subsets of X induce the same topology. The uniformity U is said to be H-singular if no distinct uniformity on X is H-equivalent to U. The self-explanatory concepts of H-coarse, H-minimal and H-maximal uniformities are defined similarly.It is well known that not all uniformities are H-singular. We show here that there is a property which obstructs H-singularity: Every H-minimal uniformity has a base of finite-dimensional uniform coverings. Besides, we provide an intrinsic characterization of H-minimal uniformities and show that they are H-coarse. This characterization of H-minimality becomes a criterion for H-singularity for all uniformities that are either complete, uniformly locally precompact or proximally fine (e.g., metrizable ones). Some relevant properties which insure H-singularity are introduced and investigated in some aspect.     

Achievable sets, brambles, and sparse treewidth obstructions

One consequence of the graph minor theorem is that for every k there exists a finite obstruction set Obs(TW?k). However, relatively little is known about these sets, and very few general obstructions are known. The ones that are known are the cliques, and graphs which are formed by removing a few edges from a clique. This paper gives several general constructions of minimal forbidden minors which are sparse in the sense that the ratio of the treewidth to the number of vertices n does not approach 1 as n approaches infinity. We accomplish this by a novel combination of using brambles to provide lower bounds and achievable sets to demonstrate upper bounds. Additionally, we determine the exact treewidth of other basic graph constructions which are not minimal forbidden minors.     

Which trees are link graphs?

The link of a vertex v of a graph G is the subgraph induced by all vertices adjacent to v. If all the links of G are isomorphic to L, then G has constant link and L is called a link graph. We investigate the trees of order p≤9 to see which are link graphs. Group theoretic methods are used to obtain constructions of graphs G with constant link L for certain trees L. Necessary conditions are derived for the existence of a graph having a given graph L as its constant link. These conditions show that many trees are not link graphs. An example is given to show that a connected graph with constant link need not be point symmetric.     

Hypercyclic tuples of operators and somewhere dense orbits

In this paper we prove that there are hypercyclic (n+1)-tuples of diagonal matrices on Cn and that there are no hypercyclic n-tuples of diagonalizable matrices on Cn. We use the last result to show that there are no hypercyclic subnormal tuples in infinite dimensions. We then show that on real Hilbert spaces there are tuples with somewhere dense orbits that are not dense, but we also give sufficient conditions on a tuple to insure that a somewhere dense orbit, on a real or complex space, must be dense.     

Conrad frames

A Conrad frame is a frame which is isomorphic to the frame C(G) of all convex ?-subgroups of some lattice-ordered group G. It has long been known that Conrad frames have the disjointification property. In this paper a number of properties are considered that strengthen the disjointification property; they are referred to as the Conrad conditions. A particularly strong form of the disjointification property, the C-frame condition, is studied in detail. The class of lattice-ordered groups G for which C(G) is a C-frame is shown to coincide with the class of pairwise splitting ?-groups. The arguments are mostly frame-theoretic and Choice-free, until one tackles the question of whether C-frames are Conrad frames. They are, but the proof is decidedly not point-free. This proof actually does more: it shows that every algebraic frame with the FIP and disjointification can be coherently embedded in a C-frame. When the discussion is restricted to normal-valued lattice-ordered groups, one is able to produce examples of coherent frames having disjointification, which are not Conrad frames.     

Real dicompactifications of ditopological texture spaces

Real dicompactifications and dicompactifications of a ditopological texture space are defined and studied.Section 2 considers nearly plain extensions of a ditopological texture space (S,S,τ,κ). Spaces that possess a nearly plain extension are shown to have a property, called here almost plainness, that is weaker than that of near plainness, but which shares with near plainness the existence of an associated plain space (Sp,Sp,τp,κp). Some properties of the class of almost plain ditopological texture spaces are established, a notion of canonical nearly plain extension of an almost plain ditopological texture space, projective and injective pre-orderings and the concept of isomorphism on such canonical nearly plain extensions are defined.In Section 3 the notion of nearly plain extension is specialized to that of real dicompactification and dicompactification, and the spaces that have such extensions are characterized. Working in terms of a specific representation of the canonical real dicompactifications and dicompactifications of a completely biregular bi-T₂ almost plain ditopological space, the interrelation between sub-T-lattices of the T-lattice of ω-preserving bicontinuous real mappings on the associated plain space and the real dicompactifications and dicompactifications are investigated. In particular generalizations of the Hewitt realcompactification and Stone-?ech compactification are obtained, and shown to be reflectors for the appropriate categories.     

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 shape of extremal functions for Poincaré-Sobolev-type inequalities in a ball

We study extremal functions for a family of Poincaré-Sobolev-type inequalities. These functions minimize, for subcritical or critical p?2, the quotient ‖∇u_‖2/‖up_‖ among all u∈H¹(B)?{0} with B_∫u=0. Here B is the unit ball in RN. We show that the minimizers are axially symmetric with respect to a line passing through the origin. We also show that they are strictly monotone in the direction of this line. In particular, they take their maximum and minimum precisely at two antipodal points on the boundary of B. We also prove that, for p close to 2, minimizers are antisymmetric with respect to the hyperplane through the origin perpendicular to the symmetry axis, and that, once the symmetry axis is fixed, they are unique (up to multiplication by a constant). In space dimension two, we prove that minimizers are not antisymmetric for large p.     

Congruence of Hermitian matrices by Hermitian matrices

Two Hermitian matrices A,B∈M_n(C) are said to be Hermitian-congruent if there exists a nonsingular Hermitian matrix C∈M_n(C) such that B=CAC. In this paper, we give necessary and sufficient conditions for two nonsingular simultaneously unitarily diagonalizable Hermitian matrices A and B to be Hermitian-congruent. Moreover, when A and B are Hermitian-congruent, we describe the possible inertias of the Hermitian matrices C that carry the congruence. We also give necessary and sufficient conditions for any 2-by-2 nonsingular Hermitian matrices to be Hermitian-congruent. In both of the studied cases, we show that if A and B are real and Hermitian-congruent, then they are congruent by a real symmetric matrix. Finally we note that if A and B are 2-by-2 nonsingular real symmetric matrices having the same sign pattern, then there is always a real symmetric matrix C satisfying B=CAC. Moreover, if both matrices are positive, then C can be picked with arbitrary inertia.     

On complete intersection toric ideals of graphs

We study the graphs G for which their toric ideals I _G are complete intersections. In particular, we prove that for a connected graph G such that I _G is a complete intersection all of its blocks are bipartite except for at most two. We prove that toric ideals of graphs which are complete intersections are circuit ideals. In this case, the generators of the toric ideal correspond to even cycles of G except of at most one generator, which corresponds to two edge disjoint odd cycles joint at a vertex or with a path. We prove that the blocks of these graphs satisfy the odd cycle condition. Finally, we characterize all complete intersection toric ideals of graphs which are normal.     

Homeomorphic measures on stationary Bratteli diagrams

We study the set S of ergodic probability Borel measures on stationary non-simple Bratteli diagrams which are invariant with respect to the tail equivalence relation R. Equivalently, the set S is formed by ergodic probability measures invariant with respect to aperiodic substitution dynamical systems. The paper is devoted to the classification of measures μ from S with respect to a homeomorphism. The properties of the clopen values set S(μ) are studied. It is shown that for every measure μ∈S there exists a subgroup G⊂R such that S(μ)=G∩[0,1]. A criterion of goodness is proved for such measures. Based on this result, the measures from S are classified up to a homeomorphism. We prove that for every good measure μ∈S there exist countably many measures {μi}_i∈N⊂S such that the measures μ and μi are homeomorphic but the tail equivalence relations on the corresponding Bratteli diagrams are not orbit equivalent.     

The p-median problem under uncertainty

Consider the need to currently locate p facilities but it is possible that up to q additional facilities will have to be located in the future. There are known probabilities that 0 ? r ? q facilities will need to be located. The p-median problem under uncertainty is to find the location of p facilities such that the expected value of the objective function in the future is minimized. The problem is formulated on a graph, properties of it are proven, an integer programming formulation is constructed, and heuristic algorithms are suggested for its solution. The heuristic algorithms are modified to reduce the run time by about two orders of magnitude with minimal effect on the quality of the solution. Optimal solutions for many problems are found effectively by CPLEX. Computational results using the heuristic algorithms are presented.     

On the Ono invariants of imaginary quadratic number fields

J. Cohen, J. Sonn, F. Sairaiji and K. Shimizu proved that there are only finitely many imaginary quadratic number fields K whose Ono invariants OnoK are equal to their class numbers hK. Assuming a Restricted Riemann Hypothesis, namely that the Dedekind zeta functions of imaginary quadratic number fields K have no Siegel zeros, we determine all these K's. There are 114 such K's. We also prove that we are missing at most one such K. M. Ishibashi proved that if OnoK is large enough compared with hK, then the ideal class groups of K is cyclic. We give a short proof and a precision of Ishibashi's result. We prove that there are only finitely many imaginary quadratic number fields K satisfying Ishibashi's sufficient condition. Assuming our Restricted Riemann Hypothesis, we prove that the absolute values dK of their discriminants are less than 2.3⋅¹⁰⁹. We determine all these K's with dK?¹⁰⁶. There are 76 such K's. We prove that there is at most one such K with dK?1.8⋅¹⁰¹¹.     

Distortion of Banach spaces and supermultiplicative operational quantities

We prove that certain operational quantities q which characterize upper-semi Fredholm operators are supermultiplicative, in the sense of that q(S)q(T)?q(ST). Based on the distortion of Banach spaces we show that another is not supermultiplicative. Moreover we introduce two supermultiplicative operational quantities which characterize also the upper-semi Fredholm operators and we prove that they are not equivalent to some operational quantities known.     

Counterexamples to a rank analog of the Shepherd-Leedham-Green-Mckay theorem on finite p-groups of maximal nilpotency class

By the Shepherd-Leedham-Green-McKay theorem on finite p-groups of maximal nilpotency class, if a finite p-group of order p ⁿ has nilpotency class n?1, then f has a subgroup of nilpotency class at most 2 with index bounded in terms of p. Some counterexamples to a rank analog of this theorem are constructed that give a negative solution to Problem 16.103 in The Kourovka Notebook. Moreover, it is shown that there are no functions r(p) and l(p) such that any finite 2-generator p-group whose all factors of the lower central series, starting from the second, are cyclic would necessarily have a normal subgroup of derived length at most l(p) with quotient of rank at most r(p). The required examples of finite p-groups are constructed as quotients of torsion-free nilpotent groups which are abstract 2-generator subgroups of torsion-free divisible nilpotent groups that are in the Mal’cev correspondence with “truncated” Witt algebras.     

On the Schröder–Bernstein property for modules

The well known Schröder–Bernstein Theorem states that any two sets with one to one maps into each other are isomorphic. The question of whether any two (subisomorphic or) direct summand subisomorphic algebraic structures are isomorphic, has long been of interest. Kaplansky asked whether direct summands subisomorphic abelian groups are always isomorphic? The question generated a great deal of interest. The study of this question for the general class of modules has been somewhat limited. We extend the study of this question for modules in this paper. We say that a module Msatisfies the Schröder–Bernstein property (S-B property) if any two direct summands of M which are subisomorphic to direct summands of each other, are isomorphic. We show that a large number of classes of modules satisfy the S-B property. These include the classes of quasi-continuous, directly finite, quasi-discrete and modules with ACC on direct summands. It is also shown that over a Noetherian ring R, every extending module satisfies the S-B property. Among applications, it is proved that the class of rings R for which every R-module satisfies the S-B property is precisely that of pure-semisimple rings. We show that over a commutative domain R, any two quasi-continuous subisomorphic R-modules are isomorphic if and only if R is a PID. We study other conditions related to the S-B property and obtain characterizations of certain classes of rings via those conditions. Examples which delimit and illustrate our results are provided.     

Isomorphism of Hilbert modules over stably finite C-algebras

It is shown that if A is a stably finite C^∗-algebra and E is a countably generated Hilbert A-module, then E gives rise to a compact element of the Cuntz semigroup if and only if E is algebraically finitely generated and projective. It follows that if E and F are equivalent in the sense of Coward, Elliott and Ivanescu (CEI) and E is algebraically finitely generated and projective, then E and F are isomorphic. In contrast to this, we exhibit two CEI-equivalent Hilbert modules over a stably finite C^∗-algebra that are not isomorphic.     

Hamiltonicity of 3-Arc Graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.     

Solution techniques for the Large Set Covering Problem

Given a finite set E and a family F={E₁,…,E_m} of subsets of E such that F covers E, the famous unicost set covering problem (USCP) is to determine the smallest possible subset of F that also covers E. We study in this paper a variant, called the Large Set Covering Problem (LSCP), which differs from the USCP in that E and the subsets E_i are not given in extension because they are very large sets that are possibly infinite. We propose three exact algorithms for solving the LSCP. Two of them determine minimal covers, while the third one produces minimum covers. Heuristic versions of these algorithms are also proposed and analysed. We then give several procedures for the computation of a lower bound on the minimum size of a cover. We finally present algorithms for finding the largest possible subset of F that does not cover E. We also show that a particular case of the LSCP is to determine irreducible infeasible sets in inconsistent constraint satisfaction problems. All concepts presented in the paper are illustrated on the k-colouring problem which is formulated as a constraint satisfaction problem.