N-free orders and minimal interval extensions

We investigate problems related to the set of minimal interval extensions of N-free orders. This leads us to a correspondence between this set for an arbitrary order and a certain set of its maximal N-free reductions. We also get a 1-1-correspondence between the set of linear extensions of an arbitrary order and the set of minimal interval extensions of the linegraph of that order. This has an algorithmic consequence, namely the problem of counting minimal interval extensions of an N-free order is #P-complete. Finally a characterization of all N-free orders with isomorphic root graph is given in terms of their lattice of maximal antichains; the lattices are isomorphic iff the root graphs agree.This work was supported by the PROCOPE Program. The first author is supported by the DFG.     

Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices

We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P. Two bijections of this type have been known:(1) The bijection between maximal chains in the antichain lattice A(P) and the linear extensions of P.(2) The bijection between maximal chains in the lattice of maximal antichains A_M(P) and minimal interval extensions of P.We discuss two approaches to associate interval orders with chains in A(P). This leads to new bijections generalizing Bijections 1 and 2. As a consequence, we characterize the chains corresponding to weak-order extensions and minimal weak-order extensions of P.Seeking for a way of representing interval reductions of P by chains we came upon the separation lattice S(P). Chains in this lattice encode an interesting subclass of interval reductions of P. Let S_M(P) be the lattice of maximal separations in the separation lattice. Restricted to maximal separations, the above bijection specializes to a bijection which nicely complements 1 and 2.(3) A bijection between maximal chains in the lattice of maximal separations S_M(P) and minimal interval reductions of P.     

Sublattices of the Lattices of Strong P-Congruences on P-Inversive Semigroups

In this paper, we describe strong P-congruences and sublattice-structure of the strong P-congruence lattice C_P(S) of a P-inversive semigroup S(P). It is proved that the set of all strong P-congruences C_P(S) on S(P) is a complete lattice. A close link is discovered between the class of P-inversive semigroups and the well-known class of regular ⋆-semigroups. Further, we introduce concepts of strong normal partition/equivalence, C-trace/kernel and discuss some sublattices of C_P(S). It is proved that the set of strong P-congruences, which have C-traces (C-kernels) equal to a given strong normal equivalence of P (C-kernel), is a complete sublattice of C_P(S). It is also proved that the sublattices determined by C-trace-equaling relation θ and C-kernel-equaling relation κ, respectively, are complete sublattices of C_P(S) and the greatest elements of these sublattices are given.     

The Forcing Convexity Number of a Graph

For two vertices u and v of a connected graph G, the set I(u,v) consists of all those vertices lying on a u-v geodesic in G. For a set S of vertices of G, the union of all sets I(u,v) for u, v S is denoted by I(S). A set S is a convex set if I(S) = S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. A convex set S in G with |S| = con(G) is called a maximum convex set. A subset T of a maximum convex set S of a connected graph G is called a forcing subset for S if S is the unique maximum convex set containing T. The forcing convexity number f(S, con) of S is the minimum cardinality among the forcing subsets for S, and the forcing convexity number f(G, con) of G is the minimum forcing convexity number among all maximum convex sets of G. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph G, f(G, con) con(G). It is shown that every pair a, b of integers with 0 a b and b is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of H × K ₂ for a nontrivial connected graph H is studied.     

Even Set Systems

In phylogenetic combinatorics, the analysis of split systems is a fundamental issue. Here, we observe that there is a canonical one-to-one correspondence between split systems on the one, and “even” set systems on the other hand, i.e., given any finite set X, we show that there is a canonical one-to-one correspondence between the set P (S (X ) ){\mathcal P (\mathcal S (X ) )} consisting of all subsets S{\mathcal S} of the set S (X){\mathcal S (X)} of all splits of the set X (that is, all 2-subsets {A, B}{\{A, B\}} of the power set P (X){\mathcal P (X)} of X for which A ⋃ B = X and A ⋂ B = 0̸ hold) and the set P ^even (P (X)){\mathcal P ^{even} (\mathcal P (X))} consisting of all subsets E of the power set P (X){\mathcal P (X)} of X for which, for each subset Y of X, the number of proper subsets of Y contained in E is even.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Partitioning a graph into convex sets

Let G be a finite simple graph. Let S⊆V(G), its closed interval I[S] is the set of all vertices lying on shortest paths between any pair of vertices of S. The set S is convex if I[S]=S. In this work we define the concept of a convex partition of graphs. If there exists a partition of V(G) into p convex sets we say that G is p-convex. We prove that it is NP-complete to decide whether a graph G is p-convex for a fixed integer p≥2. We show that every connected chordal graph is p-convex, for 1≤p≤n. We also establish conditions on n and k to decide if the k-th power of a cycle C_n is p-convex. Finally, we develop a linear-time algorithm to decide if a cograph is p-convex.     

Split orders and convex polytopes in buildings

As part of his work to develop an explicit trace formula for Hecke operators on congruence subgroups of SL₂(Z), Hijikata (1974) [13] defines and characterizes the notion of a split order in M₂(k), where k is a local field. In this paper, we generalize the notion of a split order to Mn(k) for n>2 and give a natural geometric characterization in terms of the affine building for SLn(k). In particular, we show that there is a one-to-one correspondence between split orders in Mn(k) and a collection of convex polytopes in apartments of the building such that the split order is the intersection of all the maximal orders representing the vertices in the polytope. This generalizes the geometric interpretation in the n=2 case in which split orders correspond to geodesics in the tree for SL₂(k) with the split order given as the intersection of the endpoints of the geodesic.     

Visibility graphs of staircase polygons and the weak Bruhat order,I: From visibility graphs to maximal chains

The recognition problem for visibility graphs of simple polygons is not known to be in NP, nor is it known to be NP-hard. It is, however, known to be inPSPACE. Further, every such visibility graph can be dismantled as a sequence of visibility graphs of convex fans. Any nondegenerated configuration ofn points can be associated with amaximal chain in the weak Bruhat order of the symmetric groupS _n . The visibility graph ofany simple polygon defined on this configuration is completely determined by this maximal chain via a one-to-one correspondence between maximal chains andbalanced tableaux of a certain shape. In the case of staircase polygons (special convex fans), we define a class of graphs calledpersistent graphs and show that the visibility graph of a staircase polygon is persistent. We then describe a polynomial-time algorithm that recovers a representative maximal chain in the weak Bruhat order from a given persistent graph, thus characterizing the class of persistent graphs. The question of recovering a staircase polygon from a given persistent graph, via a maximal chain, is studied in the companion paper [4]. The overall goal of both papers is to offer a characterization of visibility graphs, of convex fans. The research of J. Abello was supported by NSF Grants Nos. DCR 8603722 and DCR 8896281. This research was done while K. Kumar was at the Department of Computer Science, Texas A & M University.     

Über die Distributivität des Idealverbandes eines kommutativen Ringes

LetR be a commutative ring and (R)the lattice of all ideals ofR.. In the first part of this paper we give a sufficient condition for an ideal ofR to belong toD (R) using a certain prime ideal systemP (R). In the second part we investigateD (S) whenS is an integral extension of the integral domainR. An idealI ofS belongs toD (S) if noPP (R) containsIR.     

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.     

Intersection of maximal orthogonally starshaped polygons

Let S be a simply connected orthogonal polygon in and let P(S) denote the intersection of all maximal starshaped via staircase paths orthogonal subpolygons in S. Our result: if , then there exists a maximal starshaped via staircase paths orthogonal polygon , such that . As a corollary, P(S) is a starshaped (via staircase paths) orthogonal polygon or empty. The results fail without the requirement that the set S is simply connected. Received 1 March 1999.     

Two-Scale Homogeneous Functions in Wavelet Analysis

Two-scale homogeneous functions are functions hh satisfying h(x) = \gl h(2 x)h(x) = \gl h(2 x) for some constant \gl\gl. They form a class of special functions and include homogeneous polynomials. In this article we investigate two-scale homogeneous functions that are contained in a shift-invariant space S(f)S(\phi) where f\phi is an rr-vector of functions and satisfies a vector refinement equation. The structure of these functions is analyzed. In particular, we establish a one-to-one correspondence between these two-scale homogeneous functions with order \gl\gl and the left eigenvectors of a finite matrix (derived from the mask for f\phi) associated with eigenvalue \gl\gl.     

Join-semidistributive lattices and convex geometries

We introduce the notion of a convex geometry extending the notion of a finite closure system with the anti-exchange property known in combinatorics. This notion becomes essential for the different embedding results in the class of join-semidistributive lattices. In particular, we prove that every finite join-semidistributive lattice can be embedded into a lattice S_P(A) of algebraic subsets of a suitable algebraic lattice A. This latter construction, S_P(A), is a key example of a convex geometry that plays an analogous role in hierarchy of join-semidistributive lattices as a lattice of equivalence relations does in the class of modular lattices. We give numerous examples of convex geometries that emerge in different branches of mathematics from geometry to graph theory. We also discuss the introduced notion of a strong convex geometry that might promise the development of rich structural theory of convex geometries.     

Maximal Chains in Positive Subfamilies of P(ω)

A family P ì [w]^w{\mathcal P} \subset [\omega]^\omega is called positive iff it is the union of some infinite upper set in the Boolean algebra P(ω)/Fin. For example, if I ì P(w){\mathcal I} \subset P(\omega) is an ideal containing the ideal Fin of finite subsets of ω, then P(w) \IP(\omega) \setminus {\mathcal I} is a positive family and the set Dense(\mathbb Q)\mbox{Dense}({\mathbb Q}) of dense subsets of the rational line is a positive family which is not the complement of some ideal on P(\mathbb Q)P({\mathbb Q}). We prove that, for a positive family P{\mathcal P}, the order types of maximal chains in the complete lattice áP è{?}, ì ?\langle {\mathcal P} \cup \{\emptyset\}, \subset \rangle are exactly the order types of compact nowhere dense subsets of the real line having the minimum non-isolated. Also we compare this result with the corresponding results concerning maximal chains in the Boolean algebras P(ω) and Intalg[0,1)_{\mathbb R}\mbox{Intalg}[0,1)_{{\mathbb R}} and the poset E(\mathbb Q)E({\mathbb Q}), where E(\mathbb Q)E({\mathbb Q}) is the set of elementary submodels of the rational line.     

Hausdorff continuous interval-valued functions and quasicontinuous functions

In the paper it is shown that every Hausdorff continuous interval-valued function corresponds uniquely to an equivalence class of quasicontinuous functions. This one-to-one correspondence is used to construct the Dedekind order completion of C(X), the set of all real-valued continuous functions, when X is a compact Hausdorff topological space or a complete metric space.     

On Invariants and Strict Systems of Irreducible Polynomials Over Henselian Valued Fields

Let g(x) be a monic irreducible defectless polynomial over a henselian valued field (K, v), i.e., K(θ) is a defectless extension of (K, v) for any root θ of g(x). It is known that a complete distinguished chain for θ with respect to (K, v) gives rise to several invariants associated with g(x). Recently Ron Brown studied certain invariants of defectless polynomials by introducing strict systems of polynomial extensions. In this article, the authors establish a one-to-one correspondence between strict systems of polynomial extensions and conjugacy classes of complete distinguished chains. This correspondence leads to a simple interpretation of various results proved for strict systems. The authors give new characterizations of an invariant γ _g introduced by Brown.     

Minimal Generating Sets for Relative Ideals in Numerical Semigroups of Multiplicity Eight

Abstract

Let S be a numerical semigroup and let I be a relative ideal of S. Let S ? I denote the dual of I and let μ _S (?) represent the size of a minimal generating set. We investigate the inequality μ _S (I)μ _S (S ? I) ≥ μ _S (I + (S ? I)) under the assumption that S has multiplicity 8. We will show that if I is non-principal, then the strict inequality μ _S (I)μ _S (S ? I) > μ _S (I + (S ? I)) always holds.     

Farthest points of sets in uniformly convex banach spaces

LetS be a closed and bounded set in a uniformly convex Banach spaceX. It is shown that the set of all points inX which have a farthest point inS is dense. Letb(S) denote the set of all farthest points ofS, then a sufficient condition for to hold is thatX have the following property (I): Every closed and bounded convex set is the intersection of a family of closed balls.     

The flatness properties of <Emphasis Type="Italic">S</Emphasis>-poset <Emphasis Type="Italic">A</Emphasis>(<Emphasis Type="Italic">I</Emphasis>) and Rees factor <Emphasis Type="Italic">S</Emphasis>-posets

Let S be a pomonoid and I a proper right ideal of S. In a previous paper, using the amalgamated coproduct A(I) of two copies of _S S over I, we were able to solve one of the problems posed in S. Bulman-Fleming et al. (Commun. Algebra 34:1291–1317, 2006). In the present paper, we investigate further flatness properties of A(I). We also solve another problem stated in the paper cited above. Namely, we determine the condition under which Rees factor S-posets have property (P _w ). Research supported by nwnu-kjcxgc-03-18.