Genus polynomials and crosscap‐number polynomials for ring‐like graphs

An H‐linear graph is obtained by transforming a collection of copies of a fixed graph H into a chain. An H‐ring‐like graph is formed by binding the two end‐copies of H in such a chain to each other. Genus polynomials have been calculated for bindings of several kinds. In this paper, we substantially generalize the rules for constructing sequences of H‐ring‐like graphs from sequences of H‐linear graphs, and we give a general method for obtaining a recursion for the genus polynomials of the graphs in a sequence of ring‐like graphs. We use Chebyshev polynomials to obtain explicit formulas for the genus polynomials of several such sequences. We also give methods for obtaining recursions for partial genus polynomials and for crosscap‐number polynomials of a bar‐ring of a sequence of disjoint graphs.     

On finite lattice coverings

We consider finite lattice coverings of strictly convex bodies K. For planar centrally symmetric K we characterize the finite arrangements C _n such that conv , where C _n is a subset of a covering lattice for K (which satisfies some natural conditions). We prove that for a fixed lattice the optimal arrangement (measured with the parametric density) is either a sausage, a so-called double sausage or tends to a Wulff-shape, depending on the parameter. This shows that the Wulff-shape plays an important role for packings as well as for coverings. Further we give a version of this result for variable lattices. For the Euclidean d-ball we characterize the lattices, for which the optimal arrangement is a sausage, for large parameter. Received 19 May 1999.     

Puintuplication of Room squares

Given a strong starter for a groupG of ordern, where 3 does not dividen, a construction is given for a strong starter for the direct sum ofG and the integers modulo 5. In particular, this gives a Room square of side 5p for all non-Fermat primesp.     

On the threshold for k-regular subgraphs of random graphs

The k-core of a graph is the largest subgraph of minimum degree at least k. We show that for k sufficiently large, the threshold for the appearance of a k-regular subgraph in the Erdős-Rényi random graph model G(n,p) is at most the threshold for the appearance of a nonempty (k+2)-core. In particular, this pins down the point of appearance of a k-regular subgraph to a window for p of width roughly 2/n for large n and moderately large k. The result is proved by using Tutte’s necessary and sufficient condition for a graph to have a k-factor.     

Random permutations of countable sets

Summary The main objective of this paper is a study of random decompositions of random point configurations onR ^d into finite clusters. This is achieved by constructing for each configurationZ a random permutation ofZ with finite cycles; these cycles then form the cluster decomposition ofZ. It is argued that a good candidate for a random permutation ofZ is a Gibbs measure for a certain specification, and conditions are given for the existence and uniqueness of such a Gibbs measure. These conditions are then verified for certain random configurationsZ.     

Mixed multiplicities and the minimal number of generator of modules

Let (R,m) be a d-dimensional Noetherian local ring. In this work we prove that the mixed Buchsbaum-Rim multiplicity for a finite family of R-submodules of R^p of finite colength coincides with the Buchsbaum-Rim multiplicity of the module generated by a suitable superficial sequence, that is, we generalize for modules the well-known Risler-Teissier theorem. As a consequence, we give a new proof of a generalization for modules of the fundamental Rees’ mixed multiplicity theorem, which was first proved by Kirby and Rees in (1994, [8]). We use the above result to give an upper bound for the minimal number of generators of a finite colength R-submodule of R^p in terms of mixed multiplicities for modules, which generalize a similar bound obtained by Cruz and Verma in (2000, [5]) for m-primary ideals.     

Evolution of harmonic maps on manifolds flat at infinity

The aim of this article is to prove a global existence result with small data for the heat flow for harmonic maps from a manifold flat at infinity into a compact manifold. By flat at infinity we mean that the growth rate of the volumes of the balls on the manifold is the same as in the flat space. This is true for any manifold for small enough radius, but is in general not true when the radius of the ball grows. So prescribing such a growth rate also at infinity selects a class of manifolds on which our result holds. In this setting estimates are available for the heat kernel and its gradient on the base manifold. From such estimates it is easy to get L ^p −L ^q bounds for the heat kernel. A contraction principle argument then yields a local existence result in a suitable Sobolev space and a global existence result for small data.     

Efficient Recognition of Totally Nonnegative Matrix Cells

The space of m×p totally nonnegative real matrices has a stratification into totally nonnegative cells. The largest such cell is the space of totally positive matrices. There is a well-known criterion due to Gasca and Peña for testing a real matrix for total positivity. This criterion involves testing mp minors. In contrast, there is no known small set of minors for testing for total nonnegativity. In this paper, we show that for each of the totally nonnegative cells there is a test for membership which only involves mp minors, thus extending the Gasca and Peña result to all totally nonnegative cells.     

Random change on a Lie group and mean glaucomatous projective shape change detection from stereo pair images

In this article we develop a nonparametric methodology for estimating the mean change for matched samples on a Lie group. We then notice that for k≥5, a manifold of projective shapes of k-ads in 3D has the structure of a 3k−15 dimensional Lie group that is equivariantly embedded in a Euclidean space, therefore testing for mean change amounts to a one sample test for extrinsic means on this Lie group. The Lie group technique leads to a large sample and a nonparametric bootstrap test for one population extrinsic mean on a projective shape space, as recently developed by Patrangenaru, Liu and Sughatadasa. On the other hand, in the absence of occlusions, the 3D projective shape of a spatial k-ad can be recovered from a stereo pair of images, thus allowing one to test for mean glaucomatous 3D projective shape change detection from standard stereo pair eye images.     

On the validity of the Ginzburg-Landau equation

Summary The famous Ginzburg-Landau equation describes nonlinear amplitude modulations of a wave perturbation of a basic pattern when a control parameterR lies in the unstable regionO(ε ²) away from the critical valueR _c for which the system loses stability. Hereε>0 is a small parameter. G-L's equation is found for a general class of nonlinear evolution problems including several classical problems from hydrodynamics and other fields of physics and chemistry. Up to now, the rigorous derivation of G-L's equation for general situations is not yet completed. This was only demonstrated for special types of solutions (steady, time periodic) or for special problems (the Swift-Hohenberg equation). Here a mathematically rigorous proof of the validity of G-L's equation is given for a general situation of one space variable and a quadratic nonlinearity. Validity is meant in the following sense. For each given initial condition in a suitable Banach space there exists a unique bounded solution of the initial value problem for G-L's equation on a finite interval of theO(1/ε²)-long time scale intrinsic to the modulation. For such a finite time interval of the intrinsic modulation time scale on which the initial value problem for G-L's equation has a bounded solution, the initial value problem for the original evolution equation with corresponding initial conditions, has a unique solutionO(ε²) — close to the approximation induced by the solution of G-L's equation. This property guarantees that, for rather general initial conditions on the intrinsic modulation time scale, the behavior of solutions of G-L's equation is really inherited from solutions of the original problem, and the other way around: to a solution of G-L's equation corresponds a nearby exact solution with a relatively small error.     

On random orderings of variables for parity ordered binary decision diagrams

Ordered binary decision diagrams (OBDDs) are a model for representing Boolean functions. There is also a more powerful variant called parity OBDDs. The size of the representation of a given function depends in both these models on the chosen ordering of the variables. It is known that there are functions such that almost all orderings of their variables yield an OBDD of polynomial size, but there are also some exceptional orderings, for which the size is exponential. We prove that for parity OBDDs, the size for a random ordering and the size for the worst ordering are polynomially related. More exactly, for every ϵ>0 there is a number c>0 such that the following holds. If a Boolean function f of n variables is such that a random ordering of the variables yields a parity OBDD for f of size at most s with probability at least ϵ, where s≥n, then every ordering of the variables yields a parity OBDD for f of size at most s^c. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 233–239, 2000     

Ramsey Functions for Quasi-Progressions

 A quasi-progression of diameter n is a finite sequence for which there exists a positive integer L such that for . Let be the least positive integer such that every 2-coloring of will contain a monochromatic k-term quasi-progression of diameter n. We give a lower bound for in terms of k and i that holds for all . Upper bounds are obtained for in all cases for which . In particular, we show that . Exact formulae are found for and . We include a table of computer-generated values of , and make several conjectures. Received: September 22, 1995 / Revised: February 28, 1997     

Radicalizers

For a Kurosh–Amitsur radical class of rings, we investigate the existence, for a radical subring S of a ring A, of a largest subring T of A for which S is the radical. When T exists, it is called the radicalizer of S. There are no radical classes of associative rings for which every radical subring of every ring has a radicalizer. If a subring is the radical of its idealizer, then the idealizer is a radicalizer. We examine radical classes for which each radical subring is contained in one which is the radical of its own idealizer.     

Steiner trees for fixed orientation metrics

We consider the problem of constructing Steiner minimum trees for a metric defined by a polygonal unit circle (corresponding to σ ≥ 2 weighted legal orientations in the plane). A linear-time algorithm to enumerate all angle configurations for degree three Steiner points is given. We provide a simple proof that the angle configuration for a Steiner point extends to all Steiner points in a full Steiner minimum tree, such that at most six orientations suffice for edges in a full Steiner minimum tree. We show that the concept of canonical forms originally introduced for the uniform orientation metric generalises to the fixed orientation metric. Finally, we give an O(σ n) time algorithm to compute a Steiner minimum tree for a given full Steiner topology with n terminal leaves.     

The f-factor Problem for Graphs and the Hereditary Property

If P is a hereditary property then we show that, for the existence of a perfect f-factor, P is a sufficient condition for countable graphs and yields a sufficient condition for graphs of size ℵ₁. Further we give two examples of a hereditary property which is even necessary for the existence of a perfect f-factor. We also discuss the ℵ₂-case.This paper was supported by the Volkswagen Stiftung     

An extension theorem for slice monogenic functions and some of its consequences

Slice monogenic functions were introduced by the authors in [6]. The central result of this paper is an extension theorem, which shows that every holomorphic function defined on a suitable domain D of a complex plane can be uniquely extended to a slice monogenic function defined on a domain U _D , determined by D, in a Euclidean space of appropriate dimension. Two important consequences of the result are a structure theorem for the zero set of a slice monogenic function (with a related corollary for polynomials with coefficients in Clifford algebras), and the possibility to construct a multiplicative theory for such functions. Slice monogenic functions have a very important application in the definition of a functional calculus for n-tuples of noncommuting operators.     

Tensor factorization and Spin construction for Kac-Moody algebras

In this paper we discuss the “Factorization phenomenon” which occurs when a representation of a Lie algebra is restricted to a subalgebra, and the result factors into a tensor product of smaller representations of the subalgebra. We analyze this phenomenon for symmetrizable Kac-Moody algebras (including finite-dimensional, semi-simple Lie algebras). We present a few factorization results for a general embedding of a symmetrizable Kac-Moody algebra into another and provide an algebraic explanation for such a phenomenon using Spin construction. We also give some application of these results for semi-simple, finite-dimensional Lie algebras.We extend the notion of Spin functor from finite-dimensional to symmetrizable Kac-Moody algebras, which requires a very delicate treatment. We introduce a certain category of orthogonal g-representations for which, surprisingly, the Spin functor gives a g-representation in Bernstein-Gelfand-Gelfand category O. Also, for an integrable representation, Spin produces an integrable representation. We give the formula for the character of Spin representation for the above category and work out the factorization results for an embedding of a finite-dimensional, semi-simple Lie algebra into its untwisted affine Lie algebra. Finally, we discuss the classification of those representations for which Spin is irreducible.     

Partially ordered knapsack and applications to scheduling

In the partially ordered knapsack problem (POK) we are given a set N of items and a partial order ?_P on N. Each item has a size and an associated weight. The objective is to pack a set N^′⊆N of maximum weight in a knapsack of bounded size. N^′ should be precedence-closed, i.e., be a valid prefix of ?_P. POK is a natural generalization, for which very little is known, of the classical Knapsack problem. In this paper we present both positive and negative results. We give an FPTAS for the important case of a two-dimensional partial order, a class of partial orders which is a substantial generalization of the series-parallel class, and we identify the first non-trivial special case for which a polynomial-time algorithm exists. Our results have implications for approximation algorithms for scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times, a problem closely related to POK.     

The Logical vs. the Ontological Understanding of Conditions

According to the truth-functional analysis of conditions, to be ‘necessary for’ and ‘sufficient for’ are converse relations. From this, it follows that to be ‘necessary and sufficient for’ is a symmetric relation, that is, that if P is a necessary and sufficient condition for Q, then Q is a necessary and sufficient condition for P. This view is contrary to common sense. In this paper, I point out that it is also contrary to a widely accepted ontological view of conditions, according to which if P is a necessary and sufficient condition for Q, then Q is in no sense a condition for P; it is a mere consequence of P.     

Infinite Matroidal Version of Hall's Matching Theorem

Hall's theorem for bipartite graphs gives a necessary and sufficientcondition for the existence of a matching in a given bipartitegraph. Aharoni and Ziv have generalized the notion of matchabilityto a pair of possibly infinite matroids on the same set andgiven a condition that is sufficient for the matchability ofa given pair (M, W) of finitary matroids, where the matroidM is SCF (a sum of countably many matroids of finite rank).The condition of Aharoni and Ziv is not necessary for matchability.The paper gives a condition that is necessary for the existenceof a matching for any pair of matroids (not necessarily finitary)and is sufficient for any pair (M, W) of finitary matroids,where the matroid M is SCF.