ORDER EXTENSIONS AS ADJOINT FUNCTORS

Abstract

A standard extension (resp. standard completion) is a function Z assigning to each poset P a (closure) system ZP of subsets such that x ? y iff x belongs to every Z ε ZP with y ε Z. A poset P is Z -complete if each Z ε 2P has a join in P. A map f: P → P′ is Z—continuous if f^?1 [Z′] ε ZP for all Z′ ε ZP′, and a Z—morphism if, in addition, for all Z ε ZP there is a least Z′ ε ZP′ with f[Z] ? Z′. The standard extension Z is compositive if every map f: P → P′ with {x ε P: f(x) ? y′} ε ZP for all y′ ε P′ is Z -continuous. We show that any compositive standard extension Z is the object part of a reflector from IP_Z, the category of posets and Z -morphisms, to IR_Z, the category of Z -complete posets and residuated maps. In case of a standard completion Z, every Z -continuous map is a Z -morphism, and IR2 is simply the category of complete lattices and join—preserving maps. Defining in a suitable way so-called Z -embeddings and morphisms between them, we obtain for arbitrary standard extensions Z an adjunction between IP_Z and the category of Z -embeddings. Many related adjunctions, equivalences and dualities are studied and compared with each other. Suitable specializations of the function 2 provide a broad spectrum of old and new applications.     

ON THE IMMEDIATE EXTENSIONS OF A VALUED FIELD

Abstract

In this paper the topological methods introduced by Kaplansky and the theory of linear compactifications are used to prove a result classifying the maximal immediate extensions of a valued field. Results on the existence of a complete discrete rank n valued field of characteristic 0 with prescribed residue class field of characteristic p > 0 are discussed. By applying results of Endler and Ribenboim the existence of a valued field of characteristic 0 and having prescribed residue field of characteristic p > 0 when the value group has finite rank but need not be discrete is demonstrated.     

On a kind of curious binomial identity

As a generalization of Calkin's identity and its alternating form, we compute a kind of binomial identity involving some real number sequences and a partial sum of the binomial coefficients, from which many interesting identities follow.     

Maximum antichains in the product of chains

Let P be the poset k ₁ × ... × k _n , which is a product of chains, where n1 and k ₁ ... k _n 2. Let . P is known to have the Sperner property, which means that its maximum ranks are maximum antichains. Here we prove that its maximum ranks are its only maximum antichains if and only if either n=1 or M1. This is a generalization of a classical result, Sperner's Theorem, which is the case k ₁= ... =k _n =2. We also determine the number and location of the maximum ranks of P.Research supported in part by the National Science Foundation 10/25/83.     

Multiple extensions of a finite Euler's pentagonal number theorem and the Lucas formulas

Motivated by the resemblance of a multivariate series identity and a finite analogue of Euler's pentagonal number theorem, we study multiple extensions of the latter formula. In a different direction we derive a common extension of this multivariate series identity and two formulas of Lucas. Finally we give a combinatorial proof of Lucas’ formulas.     

Minimum cutsets for an element of a boolean lattice

An informative new proof is given for the theorem of Nowakowski that determines for all n and k the minimum size of a cutset for an element A with |A|=k of the Boolean algebra B _n of all subsets of {1,...,n}, ordered by inclusion. An inequality is obtained for cutsets for A that is reminiscent of Lubell's inequality for antichains in B _n. A new result that is provided by this approach is a list of all minimum cutsets for A.Research supported in part by NSF Grant DMS 87-01475.Research supported in part by NSF Grant DMS 86-06225 and Air Force OSR-86-0076.     

Some intersection theorems

LetL(A) be the set of submatrices of anm×n matrixA. ThenL(A) is a ranked poset with respect to the inclusion, and the poset rank of a submatrix is the sum of the number of rows and columns minus 1, the rank of the empty matrix is zero. We attack the question: What is the maximum number of submatrices such that any two of them have intersection of rank at leastt? We have a solution fort=1,2 using the followoing theorem of independent interest. Letm(n,i,j,k) = max(|F|;|G|), where maximum is taken for all possible pairs of families of subsets of ann-element set such thatF isi-intersecting,G isj-intersecting andF ansd,G are cross-k-intersecting. Then fori≤j≤k, m(n,i,j,k) is attained ifF is a maximali-intersecting family containing subsets of size at leastn/2, andG is a maximal2k?i-intersecting family. Furthermore, we discuss and Erd?s-Ko-Rado-type question forL(A), as well.     

The solution of graham’s greatest common divisor problem

The following conjecture of R. L. Graham is verified: Ifn≧n ₀, wheren ₀ is an explicitly computable constant, then for anyn distinct positive integersa ₁,a ₂, ...,a _n we have a _i /(a _i ,a _j ) ≧ ≧n, and equality holds only in two trivial cases. Here (a _i ,a _j ) stands for the greatest cnmmon divisor ofa _i anda _j .     

Riordan arrays associated with Laurent series and generalized Sheffer-type groups

A relationship between a pair of Laurent series and Riordan arrays is formulated. In addition, a type of generalized Sheffer groups is defined by using Riordan arrays with respect to power series with non-zero coefficients. The isomorphism between a generalized Sheffer group and the group of the Riordan arrays associated with Laurent series is established. Furthermore, Appell, associated, Bell, and hitting-time subgroups of the groups are defined and discussed. A relationship between the generalized Sheffer groups with respect to different type of power series is presented. The equivalence of the defined Riordan array pairs and generalized Stirling number pairs is given. A type of inverse relations of various series is constructed by using pairs of Riordan arrays. Finally, several applications involving various arrays, polynomial sequences, special formulas and identities are also presented as illustrative examples.     

Transposition generation of alternating permutations

A permutation _{1 2}... _n is alternating if ₁< ₂> ₃< ₄.... Alternating permutations are counted by the Euler numbers. Here we show that alternating permutations can be listed so that successive permutations differ by a transposition, ifn is odd. Extensions and open problems are mentioned.Research supported by the Natural Sciences and Engineering Research Council of Canada under grant A3379.     

Bijections and symmetries for the factorizations of the long cycle

We study the factorizations of the permutation (1,2,…,n)$(1,2,\dots ,n)$ into k factors of given cycle types. Using representation theory, Jackson obtained for each k   an elegant formula for counting these factorizations according to the number of cycles of each factor. In the cases k=2,3$k=2,3$ Schaeffer and Vassilieva gave a combinatorial proof of Jackson?s formula, and Morales and Vassilieva obtained more refined formulas exhibiting a surprising symmetry property. These counting results are indicative of a rich combinatorial theory which has remained elusive to this point, and it is the goal of this article to establish a series of bijections which unveil some of the combinatorial properties of the factorizations of (1,2,…,n)$(1,2,\dots ,n)$ into k factors for all k  . We thereby obtain refinements of Jackson?s formulas which extend the cases k=2,3$k=2,3$ treated by Morales and Vassilieva. Our bijections are described in terms of “constellations”, which are graphs embedded in surfaces encoding the transitive factorizations of permutations.     

RELATIVE INJECTIVITY OF MODULES AND EXCELLENT EXTENSIONS

Abstract

Yesl Any equation of conservation of the form ?_x{P(?_xφ, ?_tφ) = ?_t{Q(?_xφ, ?_tφ) is shown to admit an infinite-dimensional, Abellan group of symmetries that is not a prolongation symmetry group. Explicit equations are given for the determination of the generators of the Lle algebra of this Abellan symmetry group, and for the generators of Its underlying Poisson algebra.     

CONNEXION PROPERTIES AND FACTORISATION THEOREMS

Abstract

With the introduction of several new factorisation theorems, this paper is intended to show that previous efforts of the authors [3] [5] and of Strecker [15] to describe the factorisations involving connectedness are incomplete. In Section 1 we give a purely topological construction of such a factorisation, in which the right factor is the class of spreads and the left factor has a certain property hereditarily: crucially, not all members of the left factor need be quotients. Section 2 shows that, given a left factor consisting of onto maps in the category T of topological spaces, then the class of mappings with the relevant properties hereditarily is also a left factor, and the result of section 1 is a particular case of this. Section 3 combines the material in [3] on intrinsic connexion properties with ideas of Preuss (see [1]) on disconnectednesses to yield another range of factorisations, for example, involving the maps with strongly connected fibres; and Section 4 notes some outstánding problems which our work has provoked.     

Kinematic formulas for finite lattices

In analogy to valuation characterizations and kinematic formulas of convex geometry, we develop a combinatorial theory of invariant valuations and kinematic formulas for finite lattices. Combinatorial kinematic formulas are shown to have application to some probabilistic questions, leading in turn to polynomial identities for Möbius functions and Whitney numbers.     

Two combinatorial problems on posets

Bialostocki proposed the following problem: Let nk2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|p(n, k) and every Z _k -coloring f: P Z _k there exists either a chain or an antichain A, |A|=n and _aA f(a) 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n+k–2)²–c(k) p(n, k) (n+k–2)²+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing).     

A sperner-type theorem

Let P=P ₁×P ₂×...×P _M be the direct product of symmetric chain orders P ₁, P ₂, ..., P _M . Let F be a subset of P containing no l+1 elements which are identical in M–1 components and linearly ordered in the Mth one. Then max |F|cM ^1/2lW(P), where W(P) is the cardinality of the largest level of P, and c is independent of P, M and l. Infinitely many P show that this result is best possible for every M and l apart from the constant factor c.     

A Note on Log-Convexity of q-Catalan Numbers

The q-Catalan numbers studied by Carlitz and Riordan are polynomials in q with nonnegative coefficients. They evaluate, at q = 1, to the Catalan numbers: 1, 1, 2, 5, 14,…, a log-convex sequence. We use a combinatorial interpretation of these polynomials to prove a q-log-convexity result. The sequence of q-Catalan numbers is not q-log-convex in the narrow sense used by other authors, so our work suggests a more flexible definition of q-log convex be adopted. Received January 2, 2007