Operations on binary relations

The effects of five basic operations (asymmetrization, complementation, dualization, symmetrization, transitive closure) on binary relations are examined. Identifies between compound operations are developed (e.g. the symmetric part of the transitive closure of the complement of the transitive closure equals the transitive closure of the symmetric complement of the transitive closure), ordering aspects of compound operations are noted, and it is shown that in addition to the empty and universal relations at most 110 different relations can be generated from a given binary relation by sequential applications of the five basic operations. Moreover, 110 is the least upper bound, and none of these 110 requires more than seven applications of the basic operations for its expression. One of the potentially irreducible compound operations of length seven is cstcatc, the complement of the symmetric part of the transitive closure of the complement of the asymmetric part of the transitive closure of the complement.     

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.     

Dually normal relations on sets

In this paper, the concept of dual normal relations on sets is introduced and generalized. Intrinsic characterizations of them are obtained.     

Monoidal intervals of clones on infinite sets

Let X be an infinite set of cardinality κ. We show that if L is an algebraic and dually algebraic distributive lattice with at most 2^κ completely join irreducibles, then there exists a monoidal interval in the clone lattice on X which is isomorphic to the lattice 1+L obtained by adding a new smallest element to L. In particular, we find that if L is any chain which is an algebraic lattice, and if L does not have more than 2^κ completely join irreducibles, then 1+L appears as a monoidal interval; also, if λ?2^κ, then the power set of λ with an additional smallest element is a monoidal interval. Concerning cardinalities of monoidal intervals these results imply that there are monoidal intervals of all cardinalities not greater than 2^κ, as well as monoidal intervals of cardinality 2^λ, for all λ?2^κ.     

Playing with mixed strategies on infinite sets

We prove that the property of having a value and Vervoort's Strong Zero-One Law transfer from infinite perfect information games played with mixed strategies on finite sets to those on countable sets. Received April 2001/Final version June 2002     

Similarity relations on finite ordered sets

The number of similarity relations on a totally ordered set of n elements is shown to be C_n, the nth Catalan number. By means of a graph theoretic distinction between connected and disconnected similarity relations, the number g(n) of similarity relations on a totally ordered set of n elements under which each element is related to at least one other element is found to be (for $\text{n ? 2), 2g(n) = Σ}{}_{\mathrm{i=0}}{}^{\mathrm{n?2}}\text{(?}\text{1}\text{2}\text{)}{}^{\mathrm{i}}\text{C}{}_{\mathrm{n?i}}$ . Various other classes of similarity relations, including the class of those under which each element is related to at least k other elements (k ? 1), are considered.     

Note on large sets of infinite steiner systems

Large sets of Steiner systems S(t,k,n) exist for all finite t and k with t < k and all infinite n. The vector space analogues exist over a field F for all finite t and k with t < k provided that either v or F is infinite, and n ? 2k ? t + 1. This inequality is best possible. © 1995 John Wiley & Sons, Inc.     

Ranks of binary relations

This paper clarifies the notion of rank of a binary relation. Indeed several definitions cohabit in the literature and two of them have never been distinguished. The main results concern the comparison of these two notions. We show that the two definitions are really different, even under strong restrictive conditions about the algebraic structure of the semigroup.     

Groups of binary relations

It was shown in [3] that every finite group is the maximal subgroup of a semigroupB _x of all binary relations on some finite set X. This result is extended here to arbitrary groups.     

Hypergroups and binary relations

The paper deals with a binary relation R on a set H, where the Rosenberg partial hypergroupoid H _R is a hypergroup. It proves that if H _R is a hypergroup, S is an extension of R contained in the transitive closure of R and S ², then H _S is also a hypergroup. Corollaries for various extensions of R, the union, intersection and product constructions being employed, are then proved. If H _R and H _S are mutually associative hypergroups then is proven to be a hypergroup. Lastly, a tree and an iterative sequence of hyperoperations where k = 1, 2, ...) on its vertices are considered. A bound on the diameter of is given for each k such that is associative. Received December 18, 1998; accepted in final form February 8, 2000.     

Uniform sets for infinite measure-preserving systems

The concept of a uniform set is introduced for an ergodic, measure-preserving transformation on a non-atomic, infinite Lebesgue space. The uniform sets exist inasmuch as they generate the underlying σ-algebra. This leads to the result that every ergodic, measure-preserving transformation on a non-atomic, infinite Lebesgue space is isomorphic to a minimal homeomorphism on a locally compact metric space which admits a unique, up to scaling, invariant Radon measure.     

Large k-preserving sets in infinite graphs

Let K be a cardinal. If K χ₀, define K := K . Otherwise, let K := K + 1. We prove a conjecture of Mader: Every infinite K -connected graph G = (V, E) contains a set S ? V with |S| = |V| such that G/S is K -connected for all S? S.