Factorization in dedekind domains with finite class group

LetD be a Dedekind domain. It is well known thatD is then an atomic integral domain (that is to say, a domain in which each nonzero nonunit has a factorization as a product of irreducible elements). We study factorization properties of elements in Dedekind domains with finite class group. IfD has the property that any factorization of an elementα into irreducibles has the same length, thenD is called a half factorial domain (HFD, see [41]). IfD has the property that any factorization of an elementα into irreducibles has the same length modulor (for somer>1), thenD is called a congruence half factorial domain of orderr. In Section I we consider some general factorization properties of atomic integral domains as well as the interrelationship of the HFD and CHFD property in the Dedekind setting. In Section II we extend many of the results of [41], [42] and [36] concerning HFDs when the class group ofD is cyclic. Finally, in Section III we consider the CHFD property in detail and determine some basic properties of Dedekind CHFDs. IfG is any Abelian group andS any subset ofG−[0], then {G, S} is called a realizable pair if there exists a Dedekind domainD with class groupG such thatS is the set of nonprincipal classes ofG which contain prime ideals. We prove that for a finite abelian groupG there exists a realizable pair {G, S} such that any Dedekind domain associated to {G, S} is CHFD for somer>1 but not HFD if and only ifG is not isomorphic toZ ₂,Z ₂,Z ₂ ⊕Z ₂, orZ ₃ ⊕Z ₃. The first author received support under the John M. Bennett Fellowship at Trinity University and also gratefully acknowledges the support of The University of North Carolina at Chapel Hill.     

A Notion of Rank for Right Congruences on Semigroups

ABSTRACT

We introduce a new notion of rank for a semigroup S. The rank is associated with pairs (I,ρ), where ρ is a right congruence and I is a ρ-saturated right ideal. We allow I to be the empty set; in this case the rank of (?, ρ) is the Cantor-Bendixson rank of ρ in the lattice of right congruences of S, with respect to a topology we title the finite type topology. If all pairs have rank, then we say that S is ranked. Our notion of rank is intimately connected with chain conditions: every right Noetherian semigroup is ranked, and every ranked inverse semigroup is weakly right Noetherian.

Our interest in ranked semigroups stems from the study of the class ± b? _S of existentially closed S-sets over a right coherent monoid S. It is known that for such S the set of sentences in the language of S-sets that are true in every existentially closed S-set, that is, the theory T _S of ± b? _S , has the model theoretic property of being stable. Moreover, T _S is superstable if and only if S is weakly right Noetherian. In the present article, we show that T _S satisfies the stronger property of being totally transcendental if and only if S is ranked and weakly right Noetherian.     

Chordal Coxeter groups

A solution of the isomorphism problem is presented for the class of Coxeter groups W that have a finite set of Coxeter generators S such that the underlying graph of the presentation diagram of the system (W,S) has the property that every cycle of length at least four has a chord. As an application, we construct counterexamples to two conjectures concerning the isomorphism problem for Coxeter groups.      

The disjunctive domination number of a graph

Abstract

For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.     

A 2-basic set of the alternating group

In this note, we construct a 2-basic set of the alternating group \mathfrakA_n{\mathfrak{A}_n}. To do this, we construct a 2-basic set of the symmetric group \mathfrakS_n{\mathfrak{S}_n} with an additional property, such that its restriction to \mathfrakA_n{\mathfrak{A}_n} is a 2-basic set. We adapt here a method developed by Brunat and Gramain (J. Reine Angew. Math., to appear) for the case when the characteristic is odd. One of the main tools is the generalized perfect isometries defined by Külshammer et al. (Invent. Math. 151, 513–552, (2003)).     

A Note on Degree Conditions for Traceability in Locally Claw-Free Graphs

We say that a set S of vertices is traceable in a graph G whenever there is a path in G containing all vertices of S. In this paper we study the problem of traceability of a prescribed set of vertices in a locally claw-free graph (i.e. a graph in which some specified vertices are not centers of an induced claw). In particular we give sufficient degree conditions restricted to the given set S of vertices for the traceability of S.     

Improving the Rate of Convergence of High-Order Finite Elements on Polyhedra I: A Priori Estimates

ABSTRACT

Let 𝒯 _k be a sequence of triangulations of a polyhedron Ω ? ? ⁿ and let S _k be the associated finite element space of continuous, piecewise polynomials of degree m. Let u _k  ∈ S _k be the finite element approximation of the solution u of a second-order, strongly elliptic system Pu = f with zero Dirichlet boundary conditions. We show that a weak approximation property of the sequence S _k ensures optimal rates of convergence for the sequence u _k . The method relies on certain a priori estimates in weighted Sobolev spaces for the system Pu = 0 that we establish. The weight is the distance to the set of singular boundary points. We obtain similar results for the Poisson problem with mixed Dirichlet–Neumann boundary conditions on a polygon.     

Integer linear programming models for 2-staged two-dimensional Knapsack problems

 We are given a unique rectangular piece of stock material S, with height H and width W, and a list of m rectangular shapes to be cut from S. Each shape's type i (i = 1, ..., m) is characterized by a height , a width , a profit , and an upper bound ub _i indicating the maximum number of items of type i which can be cut. We refer to the Two-Dimensional Knapsack (TDK) as the problem of determining a cutting pattern of S maximizing the sum of the profits of the cut items. In particular, we consider the classical variant of TDK in which the maximum number of cuts allowed to obtain each item is fixed to 2, and we refer to this problem as 2-staged TDK (2TDK). For the 2TDK problem we present two new Integer Linear Programming models, we discuss their properties, and we compare them with other formulations in terms of the LP bound they provide. Finally, both models are computationally tested within a standard branch-and-bound framework on a large set of instances from the literature by reinforcing them with the addition of linear inequalities to eliminate symmetries. Received: October 17, 2000 / Accepted: December 19, 2001 Published online: September 27, 2002 Key words. packing – cutting – integer linear programming     

The GL2 Main Conjecture for Elliptic Curves without Complex Multiplication

Let G be a compact p-adic Lie group, with no element of order p, and having a closed normal subgroup H such that G/H is isomorphic to Z_p. We prove the existence of a canonical Ore set S^* of non-zero divisors in the Iwasawa algebra Λ(G) of G, which seems to be particularly relevant for arithmetic applications. Using localization with respect to S^*, we are able to define a characteristic element for every finitely generated Λ(G)-module M which has the property that the quotient of M by its p-primary submodule is finitely generated over the Iwasawa algebra of H. We discuss the evaluation of this characteristic element at Artin representations of G, and its relation to the G-Euler characteristics of the twists of M by such representations. Finally, we illustrate the arithmetic applications of these ideas by formulating a precise version of the main conjecture of Iwasawa theory for an elliptic curve E over Q, without complex multiplication, over the field F generated by the coordinates of all its p-power division points; here p is a prime at least 5 where E has good ordinary reduction, and G is the Galois group of F over Q.     

Ned sets on a hyperplane

Under study are the sets in ℝ ⁿ (NED sets) each of which does not affect the conformal capacity of any condenser with connected plates disjoint from this set. These sets are removable singularities of quasiconformal mappings, which explains our interest in them. For compact sets on a hyperplane we obtain a geometric criterion of the NED property; we point out a simple sufficient condition for an NED set in terms of the connected attainability of its points from its complement in the hyperplane. For compact sets on a hypersphere we obtain a criterion for an NED set in terms of the reduced module at a pair of points in its complement. We establish that a compact set on a hypersphere S, removable for the capacity in at least one spherical ring concentric with S and containing S, is an NED set.     

GCD-Sets in Integral Domains. II

Abstract

Let D be an integral domain and S ≠ U(D) a saturated multiplicative subset of D. We say that S is a GCD-set (resp., factorial-set) if S is a GCD-monoid (resp., factorial-monoid) under the product of D and that S is a Marot-set if every integral ideal of D intersecting S is generated by a set of elements in S. In this paper, we study Marot GCD-sets and Marot factorial-sets.     

On the complexity of reconstructing H‐free graphs from their Star Systems

In the Star System problem we are given a set system and asked whether it is realizable by the multi‐set of closed neighborhoods of some graph, i.e. given subsets S₁, S₂, …, S_n of an n‐element set V does there exist a graph G = (V, E) with {N[v]: v∈V} = {S₁, S₂, …, S_n}? For a fixed graph H the H‐free Star System problem is a variant of the Star System problem where it is asked whether a given set system is realizable by closed neighborhoods of a graph containing no H as an induced subgraph. We study the computational complexity of the H‐free Star System problem. We prove that when H is a path or a cycle on at most four vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H‐free Star System problem is NP‐complete. In particular, the problem is NP‐complete when H is either a cycle or a path on at least five vertices. This yields a complete dichotomy for paths and cycles. Copyright © 2010 John Wiley & Sons, Ltd. 68:113‐124, 2011     

On mean curvature flow with forcing

Abstract

This paper investigates geometric properties and well-posedness of a mean curvature flow with volume-dependent forcing. With the class of forcing which bounds the volume of the evolving set away from zero and infinity, we show that a strong version of star-shapedness is preserved over time. More precisely, it is shown that the flow preserves the ρ-reflection property, which corresponds to a quantitative Lipschitz property of the set with respect to the nearest ball. Based on this property we show that the problem is well-posed and its solutions starting with ρ-reflection property become instantly smooth. Lastly, for a model problem, we will discuss the flow’s exponential convergence to the unique equilibrium in Hausdorff topology. For the analysis, we adopt the approach developed by Feldman-Kim to combine viscosity solutions approach and variational method. The main challenge lies in the lack of comparison principle, which accompanies forcing terms that penalize small volume.     

Apery Sets of Numerical Semigroups #

Let S be a numerical semigroup. We examine a particular subset of the Apery set of S and establish a correspondence between this subset and the holes of S . This correspondence allows us to establish conditions for S to be almost symmetric.     

On the symmetry function of a convex set

We attempt a broad exploration of properties and connections between the symmetry function of a convex set S ${S \subset\mathbb{R}^n}We attempt a broad exploration of properties and connections between the symmetry function of a convex set S and other arenas of convexity including convex functions, convex geometry, probability theory on convex sets, and computational complexity. Given a point , let sym(x,S) denote the symmetry value of x in S: , which essentially measures how symmetric S is about the point x, and define x ^* is called a symmetry point of S if x ^* achieves the above maximum. The set S is a symmetric set if sym (S)=1. There are many important properties of symmetric convex sets; herein we explore how these properties extend as a function of sym (S) and/or sym (x,S). By accounting for the role of the symmetry function, we reduce the dependence of many mathematical results on the strong assumption that S is symmetric, and we are able to capture and otherwise quantify many of the ways that the symmetry function influences properties of convex sets and functions. The results in this paper include functional properties of sym (x,S), relations with several convex geometry quantities such as volume, distance, and cross-ratio distance, as well as set approximation results, including a refinement of the L?wner-John rounding theorems, and applications of symmetry to probability theory on convex sets. We provide a characterization of symmetry points x ^* for general convex sets. Finally, in the polyhedral case, we show how to efficiently compute sym(S) and a symmetry point x ^* using linear programming. The paper also contains discussions of open questions as well as unproved conjectures regarding the symmetry function and its connection to other areas of convexity theory. Dedicated to Clovis Gonzaga on the occasion of his 60th birthday.     

Optimizing Phylogenetic Diversity with Ecological Constraints

Given an edge-weighted tree T{\mathcal {T}} with leaf set X, define the weight of a subset S of X as the sum of the edge-weights of the minimal subtree of T{\mathcal {T}} connecting the elements in S. It is known that the problem of selecting subsets of X of a given size to maximize this weight can be solved using a greedy algorithm. This optimization problem arises in conservation biology where the weight is referred to as the phylogenetic diversity of a taxa set S. Here, we consider the extension of this problem whereby we are only interested in selecting subsets of the taxa set that are ecologically “viable”. Such subsets are specified by an acyclic digraph which represents, for example, a food web. This additional constraint makes the problem computationally hard. In this paper, we analyze the complexity of different variations of the extended problem.     

On the complexity of the disjoint paths problem

In this paper we consider the disjoint paths problem. Given a graphG and a subsetS of the edge-set ofG the problem is to decide whether there exists a family of disjoint circuits inG each containing exactly one edge ofS such that every edge inS belongs to a circuit inC. By a well-known theorem of P. Seymour the edge-disjoint paths problem is polynomially solvable for Eulerian planar graphsG. We show that (assumingPNP) one can drop neither planarity nor the Eulerian condition onG without losing polynomial time solvability. We prove theNP-completeness of the planar edge-disjoint paths problem by showing theNP-completeness of the vertex disjoint paths problem for planar graphs with maximum vertex-degree three. This disproves (assumingPNP) a conjecture of A. Schrijver concerning the existence of a polynomial time algorithm for the planar vertex-disjoint paths problem. Furthermore we present a counterexample to a conjecture of A. Frank. This conjecture would have implied a polynomial algorithm for the planar edge-disjoint paths problem. Moreover we derive a complete characterization of all minorclosed classes of graphs for which the disjoint paths problem is polynomially solvable. Finally we show theNP-completeness of the half-integral relaxation of the edge-disjoint paths problem. This implies an answer to the long-standing question whether the edge-disjoint paths problem is polynomially solvable for Eulerian graphs.Supported by Sonderforschungsbereich 303 (DFG)     

On the Extension of Isometries between Unit Spheres of E and C（Ω）

In this paper,we study the extension of isometries between the unit spheres of some Banach spaces E and the spaces C(Ω). We obtain that if the set sm.S1(E) of all smooth points of the unit sphere S1(E) is dense in S1(E),then under some condition,every surjective isometry V0 from S1(E) onto S1(C(Ω)) can be extended to be a real linearly isometric map V of E onto C(Ω).From this resultwe also obtain some corollaries. This is the first time we study this problem on different typical spaces,and the method of proof is also very different too.     

The Structure of the Reduced Product of Preinjective Modules Over a Hereditary Right Pure Semisimple Ring

Abstract

For a monoid S , a (left) S -act is a nonempty set B together with a mapping S ×B→B sending (s, b) to sb such that S (tb)?=?lpar;st)b and 1b ?=?b for all S , t?∈?S and B ?∈?B. Right S -acts A can also be defined, and a tensor product A ??? _s B (a set)can be defined that has the customary universal property with respect to balanced maps from A?×?B into arbitrary sets. Over the past three decades, an extensive theory of flatness properties has been developed (involving free and projective acts, and flat acts of various sorts, defined in terms of when the tensor product functor has certain preservation properties). A recent and complete discussion of this area is contained in the monograph Monoids, Acts and Categories by M. Kilp et al. (New York: Walter de Gruyter, 2000). To date, there have been only a few attempts to generalize this material to ordered monoids acting on partially ordered sets ( S -posets). The present paper is devoted to such a generalization. A unique decomposition theorem for S -posets is given, based on strongly convex, indecomposable S -subposets, and a structure theorem for projective S -posets is given. A criterion for when two elements of the tensor product of S -posets given, which is then applied to investigate several flatness properties.