Comparing Semigroup and Monoid Presentations for Finite Monoids

 It is known that for any finite group G given by a finite group presentation there exists a finite semigroup presentation for G of the same deficiency, i.e. satisfying . It is also known that the analogous statement does not hold for all finite monoids. In this paper we give a necessary and sufficient condition for a finite monoid M, given by a finite monoid presentation, to have a finite semigroup presentation of the same deficiency. (Received 17 April 2001; in revised form 15 September 2001)     

Characterization of Prüfer Multiplication Monoids and Domains by Means of Spectral Module Systems

 We generalize and unify several well-known characterizations of Prüfer domains and PVMDs by properties of their overrings. Received November 19, 2001; in revised form March 18, 2002 Published online August 14, 2002     

Partial Orders on Transformation Semigroups

In 1986, Kowol and Mitsch studied properties of the so-called natural partial order on T(X), the total transformation semigroup defined on a set X. In particular, they determined when two total transformations are related under this order, and they described the minimal and maximal elements of (T(X), ). In this paper, we extend that work to the semigroup P(X) of all partial transformations of X, compare with another natural partial order on P(X), characterise the meet and join of these two orders, and determine the minimal and maximal elements of P(X) with respect to each order.This author gratefully acknowledges the generous support of Centro de Matematica, Universidade do Minho, Portugal during his visit in May–June 2001.Received May 27, 2002; in revised form November 27, 2002 Published online May 16, 2003     

Random Graph Coverings I: General Theory and Graph Connectivity

In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n, we form a random graph by replacing each vertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G. The resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also "randomizing" given graphs. The main specific result that we prove here (Theorem 1) is that if is the smallest vertex degree in G, then almost all n-covers of G are -connected. In subsequent papers we will address other graph properties, such as girth, expansion and chromatic number. Received June 21, 1999/Revised November 16, 2000 RID="*" ID="*" Work supported in part by grants from the Israel Academy of Aciences and the Binational Israel-US Science Foundation.     

Natural deduction with general elimination rules

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates. Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001     

Ups and Downs of First Order Sentences on Random Graphs

whenever is a fixed positive irrational. This raises the question what zero-one valued functions on the positive irrationals arise as the limit probability of a first order sentence on these graphs. Here we prove two necessary conditions on these functions, a number-theoretic and a complexity condition. We hope to prove in a subsequent paper that these conditions together with two simpler and previously proved conditions are also sufficient and thus they constitute a characterization. Received October 2, 1998     

The Typical Growth of the kth Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of . Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002     

On the Value Distribution of Shifts of Universal Dirichlet Series

Shifts of universal Dirichlet series are jointly universal, that means, roughly speaking, they approximate simultaneously any given family of non-vanishing analytic functions. In this note we study consequences of this remarkable property on the value-distribution. Partially supported by the Foundation for Polish Science (FNP) and KBN grant 1 PO3A 00826. Partially supported by Lithuanian Foundation for Studies and Science.     

The <Emphasis Type="Italic">p</Emphasis>-Cockcroft Property of Central Extensions of Groups II

In [6], ?evik defined necessary and sufficient conditions for the presentation of a central extension of a cyclic group by an ordinary group to be p-Cockcroft, where p is a prime or 0. In this paper, as a next step of this above result, we will define the p-Cockcroft property for the presentation of a central extension of an abelian group by any group. Finally, as an application of the main result, we will present an example.     

Partial Actions of Groups on Cell Complexes

 In this paper, we study partial group actions on 2-complexes. Our results include a characterization, in terms of generating sets, of when a partial group action on a connected 2-complex has a connected globalization. Using this result, we give a short combinatorial proof that a group acting without fixed points on a connected 2-complex, with finite quotient, is finitely generated. This result is then generalized to characterize finitely generated groups as precisely those groups having a partial action, without fixed points, on a finite tree, with a connected globalization. Finally, using Bass-Serre theory, we determine when a partial group action on a graph has a globalization which is a tree. The author was supported in part by NSF-NATO postdoctoral fellowship DGE-9972697, by Praxis XXI scholarship BPD 16306 98 and by FCT through Centro de Matemática da Universidade do Porto. Received September 20, 2001; in revised form June 25, 2002     

Sums of the error term function in the mean square for ζ(s)

Sums of the form are investigated, where is the error term in the mean square formula for . The emphasis is on the case k = 1, which is more difficult than the corresponding sum for the divisor problem. The analysis requires bounds for the irrationality measure of e^2πm and for the partial quotients in its continued fraction expansion. Authors’ addresses: Y. Bugeaud, Université Louis Pasteur, Mathématiques, 7 rue René Descartes, F-67084 Strasbourg cedex, France; A. Ivić, Katedra Matematike RGF-a, Universitet u Beogradu, Đušina 7, 11000 Beograd, Serbia     

The Cheeger Constant, the Heat Kernel, and the Green Kernel of an Infinite Graph

 This paper gives a new approach to estimate the Cheeger constant, the heat kernel, and the Green kernel of the combinatorial Laplacian for an infinite graph. Received March 12, 2001; in final form July 11, 2002     

The Expected Volume of a Tetrahedron whose Vertices are Chosen at Random in the Interior of a Cube

We calculate E[V ₄(C)], the expected volume of a tetrahedron whose vertices are chosen randomly (i.e. independently and uniformly) in the interior of C, a cube of unit volume. We find

On products of <Emphasis Type="Italic">k</Emphasis> atoms

Let H be an atomic monoid. For let denote the set of all with the following property: There exist atoms (irreducible elements) u ₁, …, u _k , v ₁, …, v _m ∈ H with u ₁· … · u _k = v ₁ · … · v _m . We show that for a large class of noetherian domains satisfying some natural finiteness conditions, the sets are almost arithmetical progressions. Suppose that H is a Krull monoid with finite cyclic class group G such that every class contains a prime (this includes the multiplicative monoids of rings of integers of algebraic number fields). We show that, for every , max which settles Problem 38 in [4]. Authors’ addresses: W. Gao, Center for Combinatorics, Nankai University, Tianjin 300071, P.R. China; A. Geroldinger, Institut für Mathematik und Wissenschaftliches Rechnen, Karl-Franzens-Universit?t Graz, Heinrichstra?e 36, 8010 Graz, Austria     

Geometry of the Normal Bundle of a Submanifold*

 We study the geometric behavior of the normal bundle T ^⊥ M of a submanifold M of a Riemannian manifold . We compute explicitely the second fundamental form of T ^⊥ M and look at the relation between the minimality of T ^⊥ M and M. Finally we show that the Maslov forms with respect to a suitable connection of the pair (T ^⊥ M, are null. Received March 14, 2001; in revised form February 11, 2002     

Arithmetic mean of differences of Dedekind sums

Recently, Girstmair and Schoissengeier studied the asymptotic behavior of the arithmetic mean of Dedekind sums , as N → ∞. In this paper we consider the arithmetic mean of weighted differences of Dedekind sums in the form , where is a continuous function with , runs over , the set of Farey fractions of order Q in the unit interval [0,1] and are consecutive elements of . We show that the limit lim _Q→∞ A _h (Q) exists and is independent of h.     

Large deviation principles for Euclidean functionals and other nearly additive processes

We prove a large deviation principle for a process indexed by cubes of the multidimensional integer lattice or Euclidean space, under approximate additivity and regularity hypotheses. The rate function is the convex dual of the limiting logarithmic moment generating function. In some applications the rate function can be expressed in terms of relative entropy. The general result applies to processes in Euclidean combinatorial optimization, statistical mechanics, and computational geometry. Examples include the length of the minimal tour (the traveling salesman problem), the length of the minimal matching graph, the length of the minimal spanning tree, the length of the k-nearest neighbors graph, and the free energy of a short-range spin glass model. Received: 3 April 1999 / Revised version: 23 June 1999 / Published online: 8 May 2001     

Embedding Semigroups into Idempotent Generated Ones

We present a concrete model of the embedding due to Pastijn and Yan of a semigroup S into an idempotent generated semigroup now in terms of a Rees matrix semigroup over S¹. The paper starts with a comparison of the two embeddings. Studying the properties of this embedding, we prove that it is functorial. We show that a number of usual semigroup properties is preserved by this embedding, such as periodicity, finiteness, the cryptic property, regularity, complete semisimplicity and various local properties, but complete regularity is not one of them.     

On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001