Each complexity-two word represents every sufficiently long spike

When is an integer for which then r _l denotes the partial function , and denotes the composition monoid of all partial functions . For a pair of positive integers we study the set S(m,n) of all integers such that there exists no which satisfies . Main Theorem: S(m,n) is finite. Received June 13, 2000; accepted in final form September 25, 2000.     

Fully invariant transformations and associated groups

It is well known that the symmetric group S _ntogether with one idempotent of rank n- 1 on a finite n-element set Nserves as a set of generators for the semigroup T _nof all the total transformations on N. It is also well known that the singular part Sing _n of T _n can be generated by a set of idempotents of rank n- 1. The purpose of this paper is to begin an investigation of the way in which Sing_nand its subsemigroups can be generated by the conjugates of a subset of elements of T _n by a subgroup of S _n . We look for the smallest subset of elements of T _n that will serve and, correspondingly, for a characterization of those subgroups of S _n that will serve. Using some techniques from graph theory we prove our main result:the conjugates of a single transformation of rank n- 1 under Gsuffice to generate Sing_nif and only if Gis what we define to be a 2-block transitive subgroup of S _n .     

D n -normal semigroups of transformations

Given a subgroup G of the symmetric group S _n on n letters, a semigroup S of transformations of X _n is G-normal if G _S =G, where G _S consists of all permutations h∈S _n such that h ⁻¹ fh∈S for all f∈S. A semigroup S is G-normax if it is a maximal semigroup in the set of all G-normal semigroups. In 1996, I. Levi showed that the alternating group A _n can not serve as the group G _S for any semigroup of total transformations of X _n . In 2000 and 2001, I. Levi, D.B. McAlister and R.B. McFadden described all A _n -normal semigroups of partial transformations of X _n . Also, in 1994, I. Levi and R.B. McFadden described all S _n -normal semigroups. In this paper, we show that the dihedral group D _n may serve as the group G _S for semigroups of transformations of X _n . We characterize a large class of D _n -normax semigroups and describe certain D _n -normal semigroups.     

Complex hyperbolic hyperplane complements

We study spaces obtained from a complete finite volume complex hyperbolic n-manifold M by removing a compact totally geodesic complex (n − 1)-submanifold S. The main result is that the fundamental group of M\ S{M{\setminus} S} is relatively hyperbolic, relative to fundamental groups of the ends of M\ S{M{\setminus} S} , and M\ S{M{\setminus} S} admits a complete finite volume A-regular Riemannian metric of negative sectional curvature. It follows that for n > 1 the fundamental group of M\ S{M{\setminus} S} satisfies Mostow-type Rigidity, has solvable word and conjugacy problems, has finite asymptotic dimension and rapid decay property, satisfies Borel and Baum-Connes conjectures, is co-Hopf and residually hyperbolic, has no nontrivial subgroups with property (T), and has finite outer automorphism group. Furthermore, if M is compact, then the fundamental group of M\ S{M{\setminus} S} is biautomatic and satisfies Strong Tits Alternative.     

The clique numbers of regular graphs of matrix algebras are finite

Let F be a field, char(F)≠2, and SGL_n(F), where n is a positive integer. In this paper we show that if for every distinct elements x,yS, x+y is singular, then S is finite. We conjecture that this result is true if one replaces field with a division ring.     

Generating Sets of Finite Transformation Semigroups PK(n,r) and K (n,r)

Let P _n and T _n be the partial transformation and the full transformation semigroups on the set {1,…, n}, respectively. In this paper we find necessary and sufficient conditions for any set of partial transformations of height r in the subsemigroup PK(n, r) = {α ∈P _n : |im (α)| ≤r} of P _n to be a (minimal) generating set of PK(n, r); and similarly, for any set of full transformations of height r in the subsemigroup K(n, r) = {α ∈T _n : |im (α)| ≤r} of T _n to be a (minimal) generating set of K(n, r) for 2 ≤ r ≤ n ? 1.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Semigroups generated by a group and an idempotent

It is well known that the semigroup of all transformations on a finite set X of order n is generated by its group of units, the symmetric group, and any idempotent of rank n ? 1. Similarly, the symmetric inverse semigroup on X is generated by its group of units and any idempotent of rank n ? 1 while the analogous result is true for the semigroup of all n × n matrices over a field.

In this paper we begin a systematic study of the structure of a semigroup S generated by its group G of units and an idempotent ? . The first section consists of preliminaries while the second contains some general results which provide the setting for those which follow.

In the third section we shall investigate the situation where G is a permutation group on a set X of order n and ? is an idempotent of rank n ? 1. In particular, we shall show that any such semigroup S is regular. Furthermore we shall determine when S is an inverse or orthodox semigroup or completely regular semigroup.

The fourth section deals with a special case, that in which G is cyclic. The fifth, and last, deals with the situation where G is dihedral. In both cases, the resulting semigroup has a particularly delicate structure which is of interest in its own right. Both situations are replete with interesting combinatorial gems.

The author was led to the results of this paper by considering the output of a computer program he was writing for generating and analyzing semigroups.     

ON STABLE LINE SEGMENTS IN ALL TRIANGULATIONS OF A PLANAR POINT SET

Abstract. Let S be a set of finite plauar points. A llne segment L(p, q) with p, q E Sis called a stable line segment of S, if there is no Line segment with two endpoints in S intersecting L(p, q). In this paper, some geometric properties of the set of all stable line segments     

On Groups Associated with Transformation Semigroups

For a semigroup S of transformations (total or partial) of a finite n-element set X_n, denote by G_S the group of all the permutations h of X_n that preserve S under conjugation. It is shown that, unless S contains certain nilpotents and has a very restricted form, the alternating group Alt_n may not serve as G_S, so that Alt_n ⊆ G_S implies that G_S=S_n, and S is an S_n-normal semigroup.     

Theories of linear order

LetT be a complete theory of linear order; the language ofT may contain a finite or a countable set of unary predicates. We prove the following results. (i) The number of nonisomorphic countable models ofT is either finite or 2^ω. (ii) If the language ofT is finite then the number of nonisomorphic countable models ofT is either 1 or 2^ω. (iii) IfS ₁(T) is countable then so isS _n(T) for everyn. (iv) In caseS ₁(T) is countable we find a relation between the Cantor Bendixon rank ofS ₁(T) and the Cantor Bendixon rank ofS _n(T). (v) We define a class of modelsL, and show thatS ₁(T) is finite iff the models ofT belong toL. We conclude that ifS ₁(T) is finite thenT is finitely axiomatizable. (vi) We prove some theorems concerning the existence and the structure of saturated models. Most of the results in this paper appeared in the author’s Master of Science thesis which was prepared at the Hebrew University under the supervision of Professor H. Gaifman.     

On Restricted Leibniz Algebras

ABSTRACT

The role played by fields in relation to Galois Rings corresponds to semifields if the associativity is dropped, that is, if we consider Generalized Galois Rings instead of (associative) Galois rings. If S is a Galois ring and pS is the set of zero divisors in S, S* = S\ pS is known to be a finite {multiplicative} Abelian group that is cyclic if, and only if, S is a finite field, or S = ?/n? with n = 4 or n = p ^r for some odd prime p. Without associativity, S* is not a group, but a loop. The question of when this loop can be generated by a single element is addressed in this article.     

Symmetric inverse topological semigroups of finite rank ≤ <Emphasis Type="Italic">n</Emphasis>

We establish topological properties of the symmetric inverse topological semigroup of finite transformations of the rank ≤ n. We show that the topological inverse semigroup is algebraically h -closed in the class of topological inverse semigroups. Also we prove that a topological semigroup S with countably compact square S×S does not contain the semigroup for infinite cardinal λ and show that the Bohr compactification of an infinite topological symmetric inverse semigroup of finite transformations of the rank ≤ n is the trivial semigroup.     

On the Number of Nilpotents in the Partial Symmetric Semigroup

Abstract

In this note, we obtain and discuss formulae for the total number of nilpotent partial and nilpotent partial one–one transformations of a finite set.     

Cycles generated by sequential iterations

For any finite non-empty set Q, and for any positive integere n, we exhibit various classes of sequential transformations which realize a cyclic permutation of Qⁿ. We also present some partial results on the longest cycles generated by monotone boolean functions of n variables.     

Covering and packing in \Bbb Zn{\Bbb Z}^n and \Bbb Rn{\Bbb R}^n, (I)

Given a finite subset A{\cal A} of an additive group \Bbb G{\Bbb G} such as \Bbb Zⁿ{\Bbb Z}^n or \Bbb Rⁿ{\Bbb R}^n , we are interested in efficient covering of \Bbb G{\Bbb G} by translates of A{\cal A} , and efficient packing of translates of A{\cal A} in \Bbb G{\Bbb G} . A set S ì \Bbb G{\cal S} \subset {\Bbb G} provides a covering if the translates A + s{\cal A} + s with s ? Ss \in {\cal S} cover \Bbb G{\Bbb G} (i.e., their union is \Bbb G{\Bbb G} ), and the covering will be efficient if S{\cal S} has small density in \Bbb G{\Bbb G} . On the other hand, a set S ì \Bbb G{\cal S} \subset {\Bbb G} will provide a packing if the translated sets A + s{\cal A} + s with s ? Ss \in {\cal S} are mutually disjoint, and the packing is efficient if S{\cal S} has large density. In the present part (I) we will derive some facts on these concepts when \Bbb G = \Bbb Zⁿ{\Bbb G} = {\Bbb Z}^n , and give estimates for the minimal covering densities and maximal packing densities of finite sets A ì \Bbb Zⁿ{\cal A} \subset {\Bbb Z}^n . In part (II) we will again deal with \Bbb G = \Bbb Zⁿ{\Bbb G} = {\Bbb Z}^n , and study the behaviour of such densities under linear transformations. In part (III) we will turn to \Bbb G = \Bbb Rⁿ{\Bbb G} = {\Bbb R}^n .     

Integral trees of arbitrarily large diameters

In this paper, we construct trees having only integer eigenvalues with arbitrarily large diameters. In fact, we prove that for every finite set S of positive integers there exists a tree whose positive eigenvalues are exactly the elements of S. If the set S is different from the set {1} then the constructed tree will have diameter 2|S|.     

An estimate of the pinching constant of minimal hypersurfaces with constant scalar curvature in the unit sphere

LetM ⁿ (n>3) be a closed minimal hypersurface with constant scalar curvature in the unit sphereS ⁿ⁺¹ (1) andS the square of the length of its second fundamental form. In this paper we prove thatS>n implies estimates of the formS>n+cn−d withc≥1/4. For example, forn>17 andS>n we proveS>n+1/4n which is sharper than a recent result of the authors [5] The second author's research was supported by NNSFC, FECC and CPSF.     

New Combinatorial Descriptions of the Triangulations of Cyclic Polytopes and the Second Higher Stasheff–Tamari Posets

This paper is concerned with the d-dimensional cyclic polytope with n vertices, C(n,d), and the set of its triangulations, S(n,d). We show that there is a bijection between S(n,d) and certain partitions of the set of increasing d-tuples on the integers 1 to n–1. We give a combinatorial characterization of the second higher Stasheff–Tamari poset, which is a partial ordering of S(n,d), and we determine its 2-dimension. There is a well-known representation of triangulations of an n-gon by right bracket vectors. We generalize this to cyclic polytopes of higher dimensions.