One-sided identities for subsets of the semigroup of binary relations

We describe one-sided identity elements and subsets of the semigroup of all binary relations on a nonempty set. We obtain formulas for the number of identities for a finite set.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 8, pp. 1026–1031, August, 1990.     

Every semigroup is isomorphic to a transitive semigroup of binary relations

Every (finite) semigroup is isomorphic to a transitive semigroup of binary relations (on a finite set).

     

On generating regular elements in the semigroup of binary relations

We prove the semigroup generated by four binary relations contains all regular binary relations.     

Covering in the set of principal ideals in the semigroup of binary relations

Communicated by Boris M. Schein     

The Schützenberger group of anH-class in the semigroup of binary relations

K. A. Zaretskii has associated a lattice V(α) with each binary relation α, and he has shown that H_α is isomorphic with the group of all automorphisms of V(α) if H_α is a group. This result is extended in this paper by showing that for any binary relation α, the Schützenberger group Γ (H_α) is isomorphic with the group of all automorphisms of V(α).     

A proof of the montague-plemmons-schein theorem on maximal subgroups of the semigroup of binary relations

The theorem in question is that the group of automorphisms of a partially ordered set (X,π), π denoting the order relation on the set X, is isomorphic to the maximal subgroup of ℬ_x containing π, where ℬ_x is the semigroup of all binary relations on X. This theorem is due to Montague and Plemmons [1] for the case X finite or countably infinite, and was extended by Schein to the general case, using a theorem due to Zaretsky [4]. A proof of the general case, based on [1] and results due to Plemmons and West [3], is also given in the preceding note by Plemmons and Schein [2]. The purpose of this note is to give an entirely self-contained proof of this intersesting theorem.     

Schützenberger groups ofH-classes in the semigroup of all binary relations on a set

In a recent paper [1972], R. L. Brandon, D. W. Hardy, and G. Markowsky, showed that the Schützenberger group Γ(H) of anH-class H inB _X is isomorphic to the automorphism group of a lattice V associated with H. For H a group this result is due to K.A. Zaretskiî [1963]. In this note we show that a small modification of Zaretskiî's method for H a group simultaneously gives the result of Brandon, Hardy and Markowsky.     

A maximal chain of principal ideals in the semigroup of binary relations on a finite set

A maximal chain of F_n+3−1 principal ideals in the semigroup of the binary relations on an n-element set X is constructed by representing a binary relation as a Boolean matrix. Here F_n stands for the n-th Fibonacci number.     

One-sided variations on binary search trees

We investigate incomplete one-sided variants of binary search trees. The (normed) size of each variant is studied, and convergence to a Gaussian law is proved in each case by asymptotically solving recurrences. These variations are also discussed within the scope of the contraction method with degenerate limit equations. In an incomplete tree the size determines most other parameters of interest, such as the height and the internal path length.     

Balanced subsets of the semigroup of partial transformations

For the elements of subsets of the semigroup of partial transformations we study when the sets of commuting and noncommuting elements are of the same cardinality.     

Geometric relations between the zeros of polynomials

We consider the classical theorem of Grace, which gives a condition for a geometric relation between two arbitrary algebraic polynomials of the same degree. This theorem is one of the basic instruments in the geometry of polynomials. In some applications of the Grace theorem, one of the two polynomials is fixed. In this case, the condition in the Grace theorem may be changed. We explore this opportunity and introduce a new notion of locus of a polynomial. Using the loci of polynomials, we may improve some theorems in the geometry of polynomials. In general, the loci of a polynomial are not easy to describe. We prove some statements concerning the properties of a point set on the extended complex plane that is a locus of a polynomial.     

Powers of subsets in a finite semigroup

Communicated by Boris M. Schein     

Balanced subsets of a symmetric inverse semigroup

For elements in the subsets of some symmetric inverse semigroup we study the problem of equal cardinality for the sets of commuting and noncommuting elements.     

On binary quadratic forms with the semigroup property

A quadratic form f is said to have the semigroup property if its values at the points of the integer lattice form a semigroup under multiplication. A problem of V. Arnold is to describe all binary integer quadratic forms with the semigroup property. If there is an integer bilinear map s such that f(s(x,y)) = f(x)f(y) for all vectors x and y from the integer two-dimensional lattice, then the form f has the semigroup property. We give an explicit integer parameterization of all pairs (f,s) with the property stated above. We do not know any other examples of forms with the semigroup property.