Descending Chains and Antichains of the Unary, Linear, and Monotone Subfunction Relations

The -subfunction relations on the set of operations on a finite base set defined by function classes are examined. For certain clones on , it is determined whether the partial orders induced by the respective -subfunction relations have infinite descending chains or infinite antichains. More specifically, we investigate the subfunction relations defined by the clone of all functions on , the clones of essentially at most unary operations, the clones of linear functions on a finite field, and the clones of monotone functions with respect to the various partial orders on .     

The Gold Partition Conjecture

We present the Gold Partition Conjecture which immediately implies the – Conjecture and tight upper bound for sorting. We prove the Gold Partition Conjecture for posets of width two, semiorders and posets containing at most elements. We prove that the fraction of partial orders on an -element set satisfying our conjecture converges to when approaches infinity. We discuss properties of a hypothetical counterexample.     

Upward Three-Dimensional Grid Drawings of Graphs

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line segments representing the edges do not cross. Our aim is to produce three-dimensional grid drawings with small bounding box volume. Our first main result is that every -vertex graph with bounded degeneracy has a three-dimensional grid drawing with volume. This is the largest known class of graphs that have such drawings. A three-dimensional grid drawing of a directed acyclic graph (dag) is upward if every arc points up in the -direction. We prove that every dag has an upward three-dimensional grid drawing with volume, which is tight for the complete dag. The previous best upper bound was . Our main result concerning upward drawings is that every -colourable dag ( constant) has an upward three-dimensional grid drawing with volume. This result matches the bound in the undirected case, and improves the best known bound from for many classes of dags, including planar, series parallel, and outerplanar. Improved bounds are also obtained for tree dags. We prove a strong relationship between upward three-dimensional grid drawings, upward track layouts, and upward queue layouts. Finally, we study upward three-dimensional grid drawings with bends in the edges.Research of Vida Dujmovi is supported by NSERC. Research of David Wood is supported by the Government of Spain grant MEC SB2003-0270 and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Sober Approach Spaces are Firmly Reflective for the Class of Epimorphic Embeddings

In [2] the subconstruct of sober approach spaces was introduced and it was shown to be a reflective subconstruct of the category of approach spaces. The main result of this paper states that moreover is firmly -reflective in for the class of epimorphic embeddings. ‘Firm -reflective’ is a notion introduced in [3] by G.C.L. Brümmer and E. Giuli and is inspired by the exemplary behaviour of the usual completion in the category of Hausdorff uniform spaces with uniformly continuous maps. It means that is -reflective in and that the reflector is such that belongs to if and only if is an isomorphism. Firm -reflectiveness implies uniqueness of completion in the sense that whenever is a map with and sober, the associated is an isomorphism. Our result generalizes the fact that in the category the subconstruct of sober topological spaces is firmly reflective for the class of b-dense embeddings in . Also firmness in some other subconstructs of will be easily obtained.A. Gerlo and C. Van Olmen are research assistants at the Fund of Scientific Research Vlaanderen (FWO). E. Vandersmissen is a research assistant supported by the FWO-grant G.0244.05.     

Coherence for Product Monoids and their Actions

Let and be two monoids (algebras) in a monoidal category . Further let be a distributive law in the sense of [J. Beck, Lect. Notes Math., 80:119–140, 1969]; naturally yields a monoid . Consider a word in the symbols , , and . The first coherence theorem proved in this paper asserts that all morphisms coincide in , provided they arise as composites of morphisms which are -products of ’s ‘canonical’ structure morphisms, and of , , , , , , , and . Assume now that an object is endowed with both an -object structure , and an -object structure . Further assume that these two structures are compatible, in the sense that they naturally yield an -object . Let be a word in , , , and , which contains a single instance of , in the rightmost position. The second coherence theorem states that all morphisms coincide in , provided they arise as composites of morphisms which are -products of ’s ‘canonical’ structure morphisms, and of , , , , , , , , , and .     

Equivalence of $n$-point Gauss–Chebyshev rule and $4n$-point midpoint rule in computing the period of a Lotka–Volterra system

Two integrals (3.6), (4.7) for the period of a periodic solution of the Lotka–Volterra system are presented in terms of two inverse functions of restricted on , , respectively. In computing this period numerically, the integral (3.6), which possesses a weak singularity of the square root type at each endpoint of the integration, is an excellent example of using the Gauss–Chebyshev integration rule of the first kind; while the integral (4.7), which is an integral of a smooth periodic function over its period , is an excellent example of using the midpoint rule, but not the trapezoidal rule, suggested by Waldvogel [39, 40], due to a removable singularity of the integrand at , , , , and , respectively. This paper shows, in computing the period of a periodic solution of the Lotka–Volterra system, the -point Gauss–Chebyshev integration rule of the first kind applied to the integral (3.6) becomes the -point midpoint rule to the integral (4.7). Dedicated to R. Bruce Kellogg on the occasion of his 75th birthday.     

Branching Rules, Kostka–Foulkes Polynomials and q-multiplicities in Tensor Product for the Root Systems B n , C n and D n

The Kostka–Foulkes polynomials related to a root system can be defined as alternating sums running over the Weyl group associated to . By restricting these sums over the elements of the symmetric group when is of type or , we obtain again a class of Kostka–Foulkes polynomials. When is of type or there exists a duality between these polynomials and some natural -multiplicities and in tensor products [11]. In this paper we first establish identities for the which implies in particular that they can be decomposed as sums of Kostka–Foulkes polynomials with nonnegative integer coefficients. Moreover these coefficients are branching coefficients This allows us to clarify the connection between the -multiplicities and the polynomials defined by Shimozono and Zabrocki. Finally we show that and coincide up to a power of with the one dimension sum introduced by Hatayama and co-workers when all the parts of are equal to , which partially proves some conjectures of Lecouvey and Shimozono and Zabrocki.Presented by P. Littelmann.     

Covers and Directed Colimits

We find conditions on , a class of objects of a Grothendieck category, sufficient for the existence of -covers. The theory includes the existence of flat covers of modules.     

Nonlinear Parabolic Equations with Regularized Derivatives in Colombeau Algebra

We consider several types of nonlinear parabolic equations with singular like potential and initial data. To prove the existence-uniqueness theorems we employ regularized derivatives. As a framework we use Colombeau space and Colombeau vector space      

Two-parameter p, q-variation Paths and Integrations of Local Times

In this paper, we prove two main results. The first one is to give a new condition for the existence of two-parameter -variation path integrals. Our condition of locally bounded -variation is more natural and easy to verify than those of Young. This result can be easily generalized to multi-parameter case. The second result is to define the integral of local time pathwise and then give generalized It’s formula when is only of bounded -variation in . In the case that is of locally bounded variation in , the integral is the Lebesgue–Stieltjes integral and was used by Elworthy, Truman and Zhao. When is of only locally -variation, where , , and , the integral is a two-parameter Young integral of -variation rather than a Lebesgue–Stieltjes integral. In the special case that is independent of , we give a new condition for Meyer's formula and is defined pathwise as a Young integral. For this we prove the local time is of -variation in for each , for each almost surely (-variation in the sense of Lyons and Young, i.e. ).     

Recursively enumerable sets of polynomials over a finite field are Diophantine

We construct a Diophantine interpretation of over . Using this together with a previous result that every recursively enumerable (r.e.) relation over is Diophantine over , we will prove that every r.e. relation over is Diophantine over . We will also look at recursive infinite base fields , algebraic over . It turns out that the Diophantine relations over are exactly the relations which are r.e. for every recursive presentation.     

Nested set complexes of Dowling lattices and complexes of Dowling trees

Given a finite group G and a natural number n, we study the structure of the complex of nested sets of the associated Dowling lattice (Proc. Internat. Sympos., 1971, pp. 101–115) and of its subposet of the G-symmetric partitions which was recently introduced by Hultman (, 2006), together with the complex of G-symmetric phylogenetic trees . Hultman shows that the complexes and are homotopy equivalent and Cohen–Macaulay, and determines the rank of their top homology. An application of the theory of building sets and nested set complexes by Feichtner and Kozlov (Selecta Math. (N.S.) 10, 37–60, 2004) shows that in fact is subdivided by the order complex of . We introduce the complex of Dowling trees and prove that it is subdivided by the order complex of . Application of a theorem of Feichtner and Sturmfels (Port. Math. (N.S.) 62, 437–468, 2005) shows that, as a simplicial complex, is in fact isomorphic to the Bergman complex of the associated Dowling geometry. Topologically, we prove that is obtained from by successive coning over certain subcomplexes. It is well known that is shellable, and of the same dimension as . We explicitly and independently calculate how many homology spheres are added in passing from to . Comparison with work of Gottlieb and Wachs (Adv. Appl. Math. 24(4), 301–336, 2000) shows that is intimely related to the representation theory of the top homology of . Research partially supported by the Swiss National Science Foundation, project PP002-106403/1.     

Every Finite Topology is Generated by a Partial Pseudometric

Given any preorder on a finite set , we present an algorithm to construct a partial pseudometric on which generates in the sense that if and only if . The specialization topology generated by agrees with the topology generated by the partial pseudometric -balls, and consequently any topology on is generated by a partial pseudometric.     

Countably Complementable Linear Orderings

We say that a countable linear ordering is countably complementable if there exists a linear ordering , possibly uncountable, such that for any countable linear ordering , does not embed into if and only if embeds into . We characterize the linear orderings which are countably complementable. We also show that this property is equivalent to the countable version of the finitely faithful extension property introduced by Hagendorf. Using similar methods and introducing the notion of weakly countably complementable linear orderings, we answer a question posed by Rosenstein and prove the countable case of a conjecture of Hagendorf, namely, that every countable linear ordering satisfies the countable version of the totally faithful extension property. This research was partially supported by NSF grant DMS-0600824.     

Almost-triangular Hopf Algebras

In this paper, we consider a finite dimensional semisimple cosemisimple quasitriangular Hopf algebra with (we call this type of Hopf algebras almost-quasitriangular) over an algebraically closed field . We denote by the vector space generated by the left tensorand of . Then is a sub-Hopf algebra of . We proved that when is odd, has a triangular structure and can be obtained from a group algebra by twisting its usual comultiplication [14]; when is even, is an extension of an abelian group algebra and a triangular Hopf algebra, and may not be triangular. In general, an almost-triangular Hopf algebra can be viewed as a cocycle bicrossproduct.      

Higher Level Affine Crystals and Young Walls

Using combinatorics of Young walls, we give a new realization of arbitrary level irreducible highest weight crystals for quantum affine algebras of type , , , , , and . The irreducible highest weight crystals are realized as the affine crystals consisting of reduced proper Young walls. The notion of slices and splitting of blocks plays a crucial role in the construction of crystals.Presented by Peter Littelman.     

Skew Distributions Generated from Different Families

Following the recent paper by Gupta et al. [8], skew pdfs of the form are generated, where the pdf and the cdf are taken to be different and to come from normal, Student's , Cauchy, Laplace, logistic or the uniform distribution. The properties of the resulting distributions are studied. In particular, expressions for the th moment and the characteristic function are derived. Graphical illustrations are also provided.     

Optimal noise suppression: A geometric nature of pseudoframes for subspaces

Pseudoframes for subspaces (PFFS) is a notion of frame-like expansions for a subspace in a separable Hilbert space [11]. The spanning nature of the sequences and in a PFFS (relative to the subspace ) is generally very different from that of a frame. Incidentally, a PFFS constitutes generally a nonorthogonal projections onto . The directions of the projection determine the geometric meanings and its applications of a PFFS. PFFS also provides a means for the construction of nonorthogonal projections that arises in various linear reconstruction problems. This article is aimed at elaborations on such geometrical properties, demonstration of natural needs of nonorthogonal projections in applications and how PFFS can be applied, particularly for optimal noise suppressions. In this specific application, we show that PFFS is not only natural and sufficient but also necessary for generating an optimal solution among the class of all linear and series-based methods.      

Existence and Stability Results for Renormalized Solutions to Noncoercive Nonlinear Elliptic Equations with Measure Data

In this paper we prove the existence of a renormalized solution to a class of nonlinear elliptic problems whose prototype is